מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Dijkstra/תרגילים/מסלולים זולים עם קשת יחידה שלילית/שאלה

נתונה רשת כבישי אגרה. לכל כביש יש מספר המתאר את עלות הנסיעה בכביש.

דוגמה: בתרשים הבא, עלות הנסיעה בכביש מ1 ל2 היא $\displaystyle 1$. כבישי אגרה, עם כביש אחד שלילי.

חברת "קדמה לתורה" פתחה כביש אגרה חדש. כדי למשוך לקוחות פוטנציאליים, למשך החודש הקרוב, תשלם החברה לכל מי שיסע בכביש. נניח לכן שעלות הנסיעה בכביש זה שלילית.

דוגמה: בתרשים הקודם, עלות הנסיעה בכביש מ7 ל3 היא $\displaystyle -3$.

שימו לב: בתרגום לגרפים, מדובר בגרף מכוון וטבלת עלויות לקשתות, כך שיש בדיוק עלות שלילית אחת. הנח שאין מעגלים שליליים בגרף.

אנא מצא אלגוריתם יעיל המקבל את הגרף, טבלת עלויות לקשתות, וצומת מוצא $\displaystyle s$, ומחזיר, עבור כל צומת $\displaystyle u$, את עלות המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$.

דוגמה: בתרשים הקודם, נניח שצומת המוצא הוא $\displaystyle s=1$: המסלול הזול ביותר מ$\displaystyle s$ ל6 הוא $\displaystyle 1\rightarrow 6$,‏ ועלותו 2. המסלול הזול ביותר מ$\displaystyle s$ ל4 הוא $\displaystyle 1\rightarrow 6\rightarrow 7\rightarrow 3\rightarrow 4$,‏ ועלותו 3.