מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מסלולים זולים לכלל הזוגות/תרגילים/ווריאציה עם מחירים שליליים/תשובה

1

נניח שיש מעגל סופי מ$\displaystyle u$ כלשהו חזרה אליו, ועלות מעגל זה היא $\displaystyle -p$. אז אין שום מסלול סופי מ$\displaystyle u$ ל$\displaystyle u$ שהוא הזול ביותר, כי הספת מעגל זה תוזיל אותו ב$\displaystyle p$.

2

אלגוריתם "הכפלת מטריצות"

באלגוריתם "הכפלת מטריצות", טענו את המשפט הבא:

משפט: נקבע את $\displaystyle n$ כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא $\displaystyle d^{(n-1)}(u,v)$.

הרעיון מאחורי המשפט היה שהמסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ בהכרח קצר מ$\displaystyle n$: אם לא, אז יש צומת אחד (לפחות) שרואים אותו פעמיים. אמנם נכון שאם מחירי הקשתות לא-שליליים (כפי שהיה שם), קל לראות שאפשר להתעלם מאפשרות זו כמסלול הזול ביותר; כאן, לעומת זאת, דווקא נוכחנו שייתכן שנרצה לפגוש אותו צומת פעמיים (ֹויותר).

אלגוריתם Floyd-Warshall

באלגוריתם Floyd-Warshall, טענו את המשפט הבא:

משפט: $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=0$. $\displaystyle min\{d^{(m-1)}(u,v),d^{(m-1)}(u,m)+d^{(m-1)}(m,v)\}$, אם $\displaystyle m>1$.

קל לראות שחלקו השני של המשפט לא נכון. בזמנו טענו שאם מ $\displaystyle u$ ל$\displaystyle v$ עוברים דרך $\displaystyle m$, אז מ$\displaystyle u$ ל$\displaystyle m$ ומ$\displaystyle m$ ל$\displaystyle v$ אין צורך לעבור דרך $\displaystyle m$. כעת דווקא ראינו שמעגל כזה מ$\displaystyle m$ ל$\displaystyle m$ דווקא עלול להוזיל את המסלול.

3

אלגוריתם "הכפלת מטריצות"

פשוט יש לחזור על הרעיון הכללי, ולראות שלא השתנה כלום.

נתחיל במשפט שראינו שהשתבש בסעיף הקודם:

משפט: נקבע את $\displaystyle n$ כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא $\displaystyle d^{(n-1)}(u,v)$.

משפט זה שוב נכון. כל מסלול באורך $\displaystyle n$ (או יותר) פוגש לפחות צומת אחד פעמיים. אם אין מעגל שלילי, מסלול כזה בהכרח אינו זול יותר ממסלול אחר ללא המעגל.

כעת נתבונן במשפט הבא:

משפט: לכל $\displaystyle m$,‏ $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=1$. $\displaystyle min_{w\in V}\{d^{(m-1)}(u,w)+$ Edge-Costs[w][v]$\displaystyle \}$, אם $\displaystyle m>1$.

בהוכחת משפט זה לא הנחנו כלום לגבי סימן מחיר הקשתות. מחיר המסלול הזול ביותר באורך 1 הוא, עפ"י ההגדרה, מחיר הקשת בין שני צמתים. המסלול הזול ביותר באורך $\displaystyle m$ מורכב, עפ"ׁ ההגדרה, ממסלול באורך $\displaystyle m-1$ ועוד קשת.

אלגוריתם Floyd-Warshall

פשוט יש לחזור על [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], ולראות שלא השתנה כלום. נתחיל במשפט הבא:

משפט: נקבע את $\displaystyle n$ כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא בדיוק $\displaystyle d^{(n)}(u,v)$.

משפט זה בוודאי נכון - המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא הזול ביותר מבין המסלולים שמותר להם לעבור דרך כל צומת בגרף. נמשיך במשפט שהשתבש מקודם:

משפט: $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=0$. $\displaystyle min\{d^{(m-1)}(u,v),d^{(m-1)}(u,m)+d^{(m-1)}(m,v)\}$, אם $\displaystyle m>1$.

חלקו הראשון של המשפט נכון לפי ההגדרה. אם אין מעגלים שליליים, גם חלקו השני נכון. אם מ$\displaystyle u$ ל$\displaystyle v$ עוברים דרך $\displaystyle m$, אז אין טעמם לבדוק מסלולים שבהם מ$\displaystyle u$ ל$\displaystyle m$ או מ$\displaystyle m$ ל$\displaystyle v$ עוברים דרך $\displaystyle m$. מסלולים אלה כוללים מעגל כזה מ$\displaystyle m$ ל$\displaystyle m$, ומסלול אחר ללא מעגל זה בהכרח אינו יקר יותר.