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

נתון גרף מכוון $\displaystyle G=(V,E)$, צומת $\displaystyle s\in V$,וטבלת מחירים חיוביים לקשתות $\displaystyle E$. בשאלה זו אנו מתעניינים במסלול הזול ביותר מ-s לכל צומת $\displaystyle u\in V$.

א'

אנא הראי מקרה שבו קיים צומת $\displaystyle u\in V$, כך שאין מסלול יחיד זול ביותר מ$\displaystyle S$ ל$\displaystyle V$.

ב'

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

ג'

אנא מצאי אלגוריתם יעיל המקבל את הגרף, צומת המוצא, וטבלת העלויות, ומחזיר מערך Shortest-Cheapest. ּShortest-Cheapest[u] יכיל את מספר הצמתים במסלול הקצר ביותר מבין המסלולים הזולים ביותר מ$\displaystyle s$ ל$\displaystyle u$. אנא הוכיח את נכונות האלגוריתם ונתחי סיבוכיותו.