נניח שלפנינו תיאור של רשת באמצעות גרף משוקלל ; כיצד אפשר למצוא נתיב קצר ביותר , שיחבר בין שני צמתים נתונים ברשת ? בהמשך נציג אלגוריתם למציאת מסלול קצר ביותר בין שני צמתים בגרף משוקלל ן אך לפני שנעשה זאת , נסה את כוחך במציאת מסלולים כאלה . 4 . 1 7 ) N 61 ? באיור 4 . 18 נתון גרף משוקלל המייצג רשת תקשורת . א . מצא את המרחקים הקצרים ביותר מצומת A לכל אחד מהצמתים האחרים ברשת . ב . על-סמך סעיף א , בנה טבלת ניתוב עבור צומת A ( בטבלת הניתוב הנח שיעדי ההגעה של המנות הם צמתים , ולא מחשבים מארחים . ( פתרון הדוגמה א . להלן המרחקים הקצרים ביותר מצומת : A ב . טבלת הניתוב של צומת : A כלומר , בנתונים הקיימים , צומת A צריך לנתב דרך צומת B את כל המנות המיועדות לצמתים B עד , E ואת המנות המיועדות לצמתים F ו-ם עליו לנתב דרך צומת . G שים לב ? גם מנות המיועדות , 0-ל ינותבו דרך . B הסיבה לכך יכולה להיות שהקיבולת של הקו בין C-b A נמוכה או שהקו עמוס .
אל הספר