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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 32:
==הקלט==
 
כפי שנאמר מקודם, נניח שמחירי הקשתות נתונות ע"י טבלת עלויות. בד"כ אנו מניחים שזה נעשה על ידי [[מבני נתונים ואלגוריתמים - מחברת קורס/טבלת ערבול|טבלת ערבול]] על הקשתות, אך כאן נניח משהו שונה במקצת. נניח ש{{קוד בשורה|Edge-Costs}} היא מטריצה שלה כניסה{{קוד בשורה|Edge-Costs[u][v]}} לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך {{קוד בשורה|Nil}}, כבטבלת ערבול). הערך {{קוד בשורה|Edge-Costs[u][v]}}, הנו:
#0, אם ו<math dir = "ltr">\displaystyle \inftyu = v</math>.
הקשתות, אך כאן נניח משהו שונה במקצת. נניח ש{{קוד בשורה|Edge-Costs}} היא מטריצה שלה כניסה
{{קוד בשורה|Edge-Costs[u][v]}} לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך {{קוד בשורה|Nil}}, כבטבלת ערבול). הערך {{קוד בשורה|Edge-Costs[u][v]}}, הנו:
#0, אם {{קוד בשורה|u == v}}.
#מחיר הקשת מ{{קוד בשורה|u}} ל{{קוד בשורה|v}}, אם יש קשת כזו.
#<math dir = "ltr">\displaystyle \infty</math>, אם אין קשת כזו, ו{{קוד<math בשורה|udir != "ltr">\displaystyle u \neq v}}</math>.
{{הארה|1 =
במידה מסויימת, הוספת הכניסות ל{{קוד בשורה|Edge-Costs}} "מוסיפה" לגרף קשתות בעלות משקלים 0 ו<math dir = "ltr">\displaystyle \infty</math>.
 
ו<math dir = "ltr">\displaystyle \infty</math>.
(זה קצת מזכיר מעגלים חשמליים, בהם אם יש נתק בין שני ענפים, אז מותר להוסיף ביניהם ענף בעל התנגדות אינסופית.)}}
 
שורה 52 ⟵ 50:
 
{{משפט|תוכן =
אין הבדל בין מחירי המסלולים הזולים ביותר בגרף המקורי לאלה שבגרף ה"מוסף".}}
 
 
==הרעיון הכללי==