דף זה הוא השלישי מבין שלושה דפים העוסקים באלגוריתמים למציאת המסלול הזול ביותר בגרף מכוון בין כל שני צמתים.
|
כדאי לדעת: כל האלגוריתמים (שאותם נלמד) למציאת מסלולים זולים לכלל הזוגות מתבססים על אותו הרעיון.
- ראשית, מניחים שהקלט של הבעיה מתאר את הבעיה בצורה נוחה (לעיתים יש צורך בהוספת עוד קשתות לגרף. מסלולים זולים לכלל הזוגות עוסק בכך).
- כעת עובדים בשיטת הפרד ומשול - מוצאים את פתרונן של בעיות "גדולות" יותר בעזרת פתרונן של בעיות "קטנות" יותר. השאלה היא כיצד מגדירים מהן בעיות "קטנות" ו"גדולות":
|
באלגוריתם "הכפלת מטריצות" מצאנו אפיון רקורסיבי למסלול הזול ביותר כפונקציה של ארכו. כאן, לעומת זאת, נמצא אפיון רקורסיבי למסלולים הזולים ביותר כפונקציה של צמתי הביניים שלהם.
הגדרה:
נניח מסלול מ ל :
נאמר שהקבוצה היא קבוצת צמתי הביניים של המסלול .
|
|
שימו לב: להלן נקודה שמבלבלת חלק מהסטודנטים מדי שנה.
אנו עוסקים בגרפים בהם הצמתים הם מספרים שלמים. לכן, כל אחד מ הוא פשוט מספר שלם מהקבוצה .
|
הגדרה:
נגדיר כ את מחיר המסלול הזול ביותר מ ל מבין אלה שכל צומת ביניים שלהם שייך ל . במילים אחרות, הוא מחיר המסלול הזול ביותר מבין אלה מהצורה  כשכל שייך ל .
|
|
שימו לב: גם באלגוריתם "הכפלת מטריצות" הגדרנו . אין קשר בין ההגדרה כאן להגדרה שם.
|
דוגמה:
בגרף שראינו, שני מסלולים (מתוך מספר מסלולים) מ ל :
- המסלול
שעלותו , ושאינו עובר דרך אף צומת ביניים.
- המסלול
שעלותו , ושעובר דרך צומת הביניים .
קל לראות, לכן:


|
לפי הגדרה זו, קל מאד לאפיין את המסלולים הזולים ביותר בגרף. המשפט הבא מראה זאת.
כל שנותר כדי לפתור את הבעיה, הוא להבחין שאפשר לחשב את המסלולים הזולים (עפ"י צמתי-הביניים בהם הם משתמשים) בצורה רקורסיבית. המשפט הבא מראה זאת.
משפט:
הוא:
Edge-Costs[u][v] , אם .
, אם .
|
הוכחה:
נזכר ש
משמעו המסלול הזול ביותר מ
ל
שכל אחד מצמתי הביניים שלו לקוח מהקבוצה
אם
, אז
אינו כולל צמתי ביניים. מדובר לכן במחיר הזול ביותר הישיר מ
ל
.
אם
, אז יש שתי אפשרויות:
אינו מופיע בקבוצת צמתי הביניים (כלומר, המסלול הזול ביותר אינו עובר דרך
).
מופיע בקבוצת צמתי הביניים (כלומר, המסלול הזול ביותר אכן עובר דרך
).
במקרה הראשון, היות שלא משתמשים ב
, אז מדובר במסלול הזול ביותר מ
ל
שכל אחד מצמתי הביניים שלו לקוח מהקבוצה
, כלומר התשובה היא פשוט
.
במקרה השני, היות שמשתמשים ב
, המסלול מתחלק לשני חלקים:
- מ
ל
. בחלק זה אפשר להניח ש
אינו צומת ביניים (מדוע?). בקטע זה, לכן, התשובה היא פשוט
.
- מ
ל
. גם בחלק זה אפשר להניח ש
אינו צומת ביניים (מדוע?). גם בקטע זה, לכן, התשובה היא פשוט
.
להלן הפסוודו-קוד לאלגוריתם:
Floyd-Warshall(G, Edge-Costs, m)
1 if m == 0
2 return Edge-Costs
3 D' = Floyd-Warshall(G, Edge-Costs, m - 1)
4 n = Length( V(G) )
5 D = Make-Matrix(n, n)
6 for u in V(G)
7 for v in V(G)
8 D[u][v] = D'[u][v]
9 if D[u][v] > D'[u][m] + D'[m][v]
10 D[u][v] = D'[u][m] + D'[m][v]
11 return D
ולהלן דוגמה לשימוש בו:
1 n = Length( V(G) )
2 D = Floyd-Warshall(G, Edge-Costs, n)
# Prints 2.
3 Print( D[1][2] )
# Prints ∞.
4 Print( D[2][1] )
ראשית, קל לראות כי 6-10 הן
, והן למעשה קובעות את זמן הריצה של קריאה יחידה של הפונקציה.
נגדיר כ
את מספר צמתי הגרף, וכ
את זמן הריצה של Floyd-Warshall(G, Edge-Costs, m)
.
אז
, ולכן
.