(1) כתבו אלגוריתם המוצא בגרף ממושקל (אי־שלילי) כלשהו, שבו n קודקודים מ־v₀ עד v_n-1 וקודקוד בגרף – v_j, את המסלולים הקצרים (הקלים) ביותר מקודקוד v_j שבגרף אל שאר הקודקודים שבגרף.

(2) מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם.

בעבור גרף G הנתון, מצאו בעזרת האלוגריתם שכתבתם את המסלול הקצר ביותר מקודקוד S לכל אחד מן הקודקודים, וסרטטו טבלת מעקב כמפורט:

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

בעבור גרף G הנתון, סרטטו את עץ המסלולים הקצרים (מקודקוד S).