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

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

הבעיה

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

הקלט

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

1. 0, אם $u=v$.
2. מחיר הקשת מתבנית:קוד בשורה לתבנית:קוד בשורה, אם יש קשת כזו.
3. $\mathrm{\infty }$, אם אין קשת כזו, ו$u\ne v$.

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