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

דף זה הוא הראשון מבין שלושה דפים העוסקים באלגוריתמים למציאת המסלול הזול ביותר בגרף מכוון בין כל שני צמתים.

כדאי לדעת: #באלגוריתם Dijkstra עסקנו בבעיה דומה, אלא ששם היינו צריכים למצוא את המסלולים הזולים מצומת מוצא מסוים, ולא בין כל שני זוגות כמו כאן. בספר הקורס, הפרק "All-Pairs Shortest Paths" מכסה נושא זה.

הבעיה

נתונים גרף מכוון $\displaystyle G=(V,E)$ וטבלת עלויות לקשתות $\displaystyle E$. בהינתן צמתים $\displaystyle u,v\in V$, רוצים למצוא את המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$.

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

דוגמה: בגרף בתרשים הבא, המספר המצויין על כל קשת הוא עלות הקשת. בעיית המסלולים הזוגים לכלל הזוגות. המסלול הזול ביותר מ$\displaystyle 1$ ל$\displaystyle 2$, לדוגמה, הוא $\displaystyle 1\rightarrow 4\rightarrow 2$, ועלותו 2. המסלול הזול ביותר מ$\displaystyle 2$ ל$\displaystyle 4$, לדוגמה, הוא $\displaystyle 2\rightarrow 3\rightarrow 4$, ועלותו 11. אין מסלול מ$\displaystyle 2$ ל$\displaystyle 1$, ולכן עלות המסלול הזול ביותר היא $\infty$.

הקלט

כפי שנאמר מקודם, נניח שמחירי הקשתות נתונות ע"י טבלת עלויות. בד"כ אנו מניחים שזה נעשה על ידי טבלת ערבול על הקשתות, אך כאן נניח משהו שונה במקצת. נניח שEdge-Costs היא מטריצה שלה כניסהEdge-Costs[u][v] לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil, כבטבלת ערבול). הערך Edge-Costs[u][v], הוא:

1. 0, אם $\displaystyle u=v$.
2. מחיר הקשת מu לv, אם יש קשת כזו.
3. $\displaystyle \infty$, אם אין קשת כזו, ו$\displaystyle u\neq v$.

כדאי לדעת: במידה מסויימת, הוספת הכניסות לEdge-Costs "מוסיפה" לגרף קשתות בעלות משקלים 0 ו$\displaystyle \infty$. סטודנטים להנדסה יזהו אולי דמיון למעגלים חשמליים, בהם: אם יש נתק בין שני ענפים, מותר להוסיף ביניהם ענף בעל התנגדות אינסופית. מותר להוסיף בין כל שתי נקודות בעלי פוטנציאל זהה (בפרט, כששתי הנקודות למעשה אותה נקודה) ענף בעל התנגדות 0.

דוגמה: בתרשים הבא, A מראה שוב את הגרף שראינו לעיל. B מראה קשתות ש"נוספו" בגלל 3, וC קשתות ש"נוספו" בגלל 2. הקלט לבעיה.

קל לראות שהתוספות הנ"ל אינן משנות דבר משמעותי:

משפט: אין הבדל בין מחירי המסלולים הזולים ביותר בגרף המקורי לאלה שבגרף ה"מוסף".

הרעיון הכללי

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

הפרק הקודם: אלגוריתם Dijkstra

מסלולים זולים לכלל הזוגות תרגילים

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