דף זה הוא השלישי מבין שלושה דפים העוסקים באלגוריתמים למציאת המסלול הזול ביותר בגרף מכוון בין כל שני צמתים.
כדאי לדעת:
כל האלגוריתמים (שאותם נלמד) למציאת מסלולים זולים לכלל הזוגות מתבססים על אותו הרעיון.
ראשית, מניחים שהקלט של הבעיה מתאר את הבעיה בצורה נוחה (לעיתים יש צורך בהוספת עוד קשתות לגרף. מסלולים זולים לכלל הזוגות עוסק בכך).
כעת עובדים בשיטת הפרד ומשול - מוצאים את פתרונן של בעיות "גדולות" יותר בעזרת פתרונן של בעיות "קטנות" יותר. השאלה היא כיצד מגדירים מהן בעיות "קטנות" ו"גדולות":
באלגוריתם "הכפלת מטריצות" נראה שיטה לפיה פותרים בעיות קטנות יותר, בהן המסלול הזול ביותר מוגבל באורך.
באלגוריתם Floyd-Warshall נראה שיטה לפיה פותרים בעיות קטנות יותר, בהן המסלול הזול ביותר מוגבל בקבוצות צמתי הביניים של המסלול.
באלגוריתם "הכפלת מטריצות" מצאנו אפיון רקורסיבי למסלול הזול ביותר כפונקציה של ארכו. כאן, לעומת זאת, נמצא אפיון רקורסיבי למסלולים הזולים ביותר כפונקציה של צמתי הביניים שלהם.
הגדרה:
נניח מסלול מ ל:
נאמר שהקבוצה היא קבוצת צמתי הביניים של המסלול .
שימו לב:
להלן נקודה שמבלבלת חלק מהסטודנטים מדי שנה.
אנו עוסקים בגרפים בהם הצמתים הם מספרים שלמים. לכן, כל אחד מ הוא פשוט מספר שלם מהקבוצה .
דוגמה:
להלן הגרף המקורי לבעיה:
בעיית המסלולים הזוגים לכלל הזוגות.
(נזכר שהגרף ה"מוסף" נוצר על ידי הוספת קשתות במחירים 0 ואינסוף.)
במסלול , קבוצת צמתי הביניים היא .
במסלול , קבוצת צמתי הביניים היא .
במסלול , קבוצת צמתי הביניים היא (הקבוצה הריקה).
במסלול , קבוצת צמתי הביניים היא .
הגדרה:
נגדיר כ את מחיר המסלול הזול ביותר מ ל מבין אלה שכל צומת ביניים שלהם שייך ל. במילים אחרות, הוא מחיר המסלול הזול ביותר מבין אלה מהצורה כשכל שייך ל.
ראשית, קל לראות כי 6-10 הן , והן למעשה קובעות את זמן הריצה של קריאה יחידה של הפונקציה.
נגדיר כ את מספר צמתי הגרף, וכ את זמן הריצה של Floyd-Warshall(G, Edge-Costs, m).
אז
, ולכן
.