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