מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/מסלולים זולים לכלל הזוגות
דף זה הוא הראשון מבין שלושה דפים העוסקים באלגוריתמים למציאת המסלול הזול ביותר בגרף מכוון בין כל שני צמתים.
![]() |
כדאי לדעת: #באלגוריתם Dijkstra עסקנו בבעיה דומה, אלא ששם היינו צריכים למצוא את המסלולים הזולים מצומת מוצא מסוים, ולא בין כל שני זוגות כמו כאן.
|
הבעיה עריכה
נתונים גרף מכוון וטבלת עלויות לקשתות . בהינתן צמתים , רוצים למצוא את המסלול הזול ביותר מ ל .
שימו לב: בדף זה לא נעסוק במחירי קשתות שאינם חיוביים. |
הקלט עריכה
כפי שנאמר מקודם, נניח שמחירי הקשתות נתונות ע"י טבלת עלויות. בד"כ אנו מניחים שזה נעשה על ידי טבלת ערבול על הקשתות, אך כאן נניח משהו שונה במקצת. נניח שEdge-Costs
היא מטריצה שלה כניסהEdge-Costs[u][v]
לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil
, כבטבלת ערבול). הערך Edge-Costs[u][v]
, הוא:
- 0, אם .
- מחיר הקשת מ
u
לv
, אם יש קשת כזו. - , אם אין קשת כזו, ו .
כדאי לדעת: במידה מסויימת, הוספת הכניסות לEdge-Costs "מוסיפה" לגרף קשתות בעלות משקלים 0 ו .
סטודנטים להנדסה יזהו אולי דמיון למעגלים חשמליים, בהם:
|
דוגמה: בתרשים הבא, A מראה שוב את הגרף שראינו לעיל. B מראה קשתות ש"נוספו" בגלל 3, וC קשתות ש"נוספו" בגלל 2. |
קל לראות שהתוספות הנ"ל אינן משנות דבר משמעותי:
משפט: אין הבדל בין מחירי המסלולים הזולים ביותר בגרף המקורי לאלה שבגרף ה"מוסף". |
הרעיון הכללי עריכה
כדאי לדעת: כל האלגוריתמים (שאותם נלמד) למציאת מסלולים זולים לכלל הזוגות מתבססים על אותו הרעיון.
|
הפרק הקודם: אלגוריתם Dijkstra |
מסלולים זולים לכלל הזוגות תרגילים |
הפרק הבא: אלגוריתם "הכפלת מטריצות" |