|
|
صفحة: 232
4 . 3 . 2 מציאת המסלול הקצר ביותר בגרף נניח שלפנינו תיאור של רשת באמצעות גרף משוקלל ; כיצד אפשר למצוא נתיב קצר ביותר , שיחבר בין שני צמתים נתונים ברשת ? בהמשך נציג אלגוריתם למציאת מסלול קצר ביותר בין שני צמתים בגרף משוקלל ן אך לפני שנעשה זאת , נסה את כוחך במציאת מסלולים כאלה . בהס מצומת A לצומת . E לכל נתיב כזה יש מחיר שנקבע לפי סכום המחירים של הצלעות המרכיבות אותו . להלן מפורטים ארבעה נתיבים אפשריים המקשרים בין צומת A לצומת E ומחיריהם ( הנתיבים מיוצגים על-ידי רשימת הצמתים משמאל לימין ) ו הנתיב הקצר ביותר הוא . ABCDE שים לב , במונח 'קצר' איננו מתכוונים למספר הצמתים שבנתיב , אלא למחירו , לפי אמת המידה שנקבעה . איור 4 . 17 גרף משוקלל המייצג רשת תקשורת
|
|