מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם 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$. אנא הוכיח את נכונות האלגוריתם ונתחי סיבוכיותו.

תשובה

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

קביעת מסלולים זולים לא-ייחודיים

שאלה

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

תשובה

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

מסלולים זולים קצרים ביותר

שאלה

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

תשובה

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

מציאת מסלול זול בגרף בעל קשתות בתחום שלם קטן

שאלה

$\displaystyle k$ הוא קבוע שלם חיובי כלשהו (לדוגמה 3), שאינו גדל יחד עם שאר הנתונים בשאלה (כגון מספר הצמתים או הקשתות).

נתונים גרף מכוון $\displaystyle G=(V,E)$ ברשימת שכנויות, טבלת עלויות לקשתות $\displaystyle E$, וצומת מוצא $\displaystyle s\in V$ כלשהו. ידוע שעלות כל קשת היא מספר שלם חיובי כלשהו הלקוח מהתחום $\displaystyle [1,k]$.

בהינתן צומת $\displaystyle v\in V$ כלשהו, רוצים לדעת מהו המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle v$. אנא כתוב אלגוריתם יעיל לצורך כך.

תשובה

נבנה גרף חדש $\displaystyle G'=(V',E')$ ברשימת שכנויות.

נגדיר את הגרף החדש מתוך $\displaystyle G=(V,E)$ כלהלן. ראשית, אם $\displaystyle V=\{1,...,n\}$, אז נקבע $\displaystyle V'=\{1,...,n\}$. כעת נעבור על כל $\displaystyle e\in E$. אם מחיר קשת $\displaystyle e$ הוא 1, נוסיף קשת זו ל$\displaystyle E'$.

לחלופין, נניח שמחיר הקשת $\displaystyle e=(u,v)$ הוא $\displaystyle k>1$. במקרה זה נוסיף עוד $\displaystyle k-1$ צמתים חדשים ל$\displaystyle V'$ ועוד $\displaystyle k$ קשתות ל$\displaystyle E'$, כך שיש מסלול באורך $\displaystyle k$ מ$\displaystyle u$ ל$\displaystyle v$ של קשתות במחיר 1 ב$\displaystyle G'$. נקבל ב$\displaystyle G'$ גרף בעל מסלולים במחיר 1 בלבד.

דוגמה: בתרשים הבא, הגרף העליון הוא $\displaystyle G$, הגרף המקורי. הגרף התחתון הוא $\displaystyle G'$ הגרף החדש (הצמתים המקוריים מ$\displaystyle G$ מסומנים בהדגשה). הפיכת Dijkstra לBFS.

המשפט הבא טריביאלי:

משפט: לכל $\displaystyle u\in V$, מחיר המסלול הזול מ$\displaystyle s$ ל$\displaystyle u$ ב$\displaystyle G$ הוא מרחק המסלול הקצר מ$\displaystyle s$ ל$\displaystyle u$ ב$\displaystyle G'$.

קל גם להווכח שסיבוכיות בניית $\displaystyle G'$ היא $\displaystyle O(k\cdot (|V|+|E|))=O(|V|+|E|)$. כעת נריץ את אלגוריתם [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] על $\displaystyle G'$. הסיבוכיות הכוללת (של הבניה ושל ההרצה) במקרה הגרוע היא $\displaystyle \Theta (k\cdot (|V|+|E|))=\Theta (|V|+|E|)$.

מציאת מספר מסלולים שונים

שאלה

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

שימו לב: הפלט של האלגוריתם הוא פשוט מספר שלם לא-שלילי.

תשובה

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

Dijkstra עם המסלולים הזולים ביותר

שאלה

בהרצאה ראינו את אלגוריתם Dijkstra בגרסה המחזירה רק את מחירי המסלולים הזולים ביותר. נזכר בממשק ובשימוש בו. נניח שהגרף הוא המתואר בתרשים הבא:

בעיית המסלול הזול ביותר.

אז קטע הקוד הבא מדגים שימוש אפשרי:

1		Min-Costs = Dijkstra(G, Edge-Costs, 1)

	# Prints 0.
2	Print( Min-Costs[1] )

	# Prints 6.
3	Print( Min-Costs[3] )

כעת רוצים לשנות את האלגוריתם Dijkstra כך שיחזיר זוג מערכים: הראשון ממפה כל צומת לעלותו המינימלית מs (כמו שעושה המערך היחיד המוחזר עד כה), והשני ממפה כל צומת למסלול עלות מינמלי מs אליו.

אם הגרף הוא הגרף שראינו לעיל, אז קטע הקוד הבא מדגים שימוש אפשרי בגרסה החדשה:

Print-Path(Path)
1	for i in [1, ..., Length(Path)]
2		Print Path[i]



1	(Min-Costs, Min-Paths) = Dijkstra(G, 1)

	# Prints 0
2	Print( Min-Costs[1] )

	# Prints nothing
3	Print-Path( Min-Paths[1] )

	# Prints 6
4	Print( Min-Costs[3] )

	# Prints (1, 6), (6, 7), (7, 3)
5	Print-Path( Min-Paths[3] )
		
	# Prints 9
6	Print( Min-Costs[4] )

	# Prints (1, 6), (6, 7), (7, 3), (3, 4)
7	Print-Path( Min-Paths[4] )

אנא כתוב את השינויים המתאימים ונתח את הסיבוכיות.

תשובה

ראשית נכתוב פונקציה דומה למה שהתבקשנו לעשות, Dijkstra'. פונקציה זו תחזיר זוג מערכים:

1. המערך הראשון הוא Min-Costs, שממפה כל צומת u לעלות המסלול הזול ביותר מs לu.
2. המערך הראשון הוא Parents, שממפה כל צומת u

לצומת הקודם במסלול הזול ביותר מs לu.להלן הפסוודו-קוד המתאים (השינויים מודגשים כך):

Dijkstra'(G, s)
1	pq = Make-Priority-Queue()
2	'''Parents = Make-Array( Length(V(G)) )'''

3	Min-Costs = Make-Array( Length(V(G)) )

4	for u in V(G)
5		Min-Costs[u] = u == s? 0 : ∞
6		'''Parents[u] = Nil'''
7		Insert(pq, u)
		
8	while Size(pq) > 0
9		u = Delete(pq)

10		for v in A(g, u)
11			if Min-Costs[v] > Min-Costs[u] + Edge-Costs[ (u, v) ]
12				Min-Costs[v] = Min-Costs[u] + Edge-Costs[ (u, v) ]
13	        	'''Parents[v] = u'''
14				Decrease-Key(pq, v)
	                	
15	return '''(Min-Dists, Parents)'''

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

נכתוב גם פונקציה Parents-To-Paths ההופכת את מערך האבות Parents למערך מסלולים.

Parents-To-Path(s, v, Parents)
1	stk = Make-Stack()
	
2	while Parents[v] != Nil
3		u = Parents[v]
4		Push(stk, (u, v))
5		v = u

6	Path = Make-Array( Size(stk) )

7	i = 1
8	while Size(stk) > 0
9		Path[i++] = Pop(stk)

10	return Path

הפונקציה מקבלת את צומת המוצא s, צומת כלשהו v, והמערך Parents; היא מחזירה מערך המתאר הת המסלול מs לv.‏ 1-6 "מטיילות" אחורה על מסלול האבות, ומכניסות קשתות למחסנית. 7-11 ממירות את המחסנית למערך, ומחזירות את המערך.

כעת, בעזרת Dijkstra' וParents-To-Paths, נוכל לכתוב את הפונקציה המבוקשת:

Dijkstra(G, s)
1	(Min-Costs, Parents) = Dijkstra'(G, s)

2	Min-Paths = Make-Array( Length(V(G)) )		

3	for v in V(G)
4		Min-Paths[u] = Parents-To-Paths(s, v, Parents)
	
5	return (Min-Costs, Min-Paths)

כעת ננתח את הסיבוכיות:

1. מהתבוננות בDijkstra', קל לראות שהסיבוכיות שלה הנה זו של אלגוריתם Dijkstra.
2. Parents-To-Paths היא $\displaystyle O(|E|)$.הסיבוכיות הכוללת, לכן, היא $\displaystyle O((|V|+|E|)\cdot \log(|V|)+|V|\cdot |E|))$.

Dijkstra על מסלולים אדומים-שחורים

שאלה

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

אנא תאר אלגוריתם כזה, ונתח את סיבוכיותו.

דוגמה: בגרף הבא, הקשתות המודגשות שחורות, וצומת המוצא הוא 1. הבעייה. בגרף זה, המסלול הקביל הזול ביותר מ1 ל4 הוא $\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4$, ועלותו 14. שים לב שהמסלול $\displaystyle 1\rightarrow 6\rightarrow 7\rightarrow 3\rightarrow 4$ אמנם זול יותר, אך פשוט אינו קביל. באותו אופן, אין מסלול קביל מ1 ל6, ולכן עלות 6 היא $\displaystyle \infty$.

תשובה

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. כל קשת אדומה בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין $\displaystyle u$ ב$\displaystyle A$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
2. כל קשת שחורה בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.

התרשים הבא מראה זאת.

הוספת הקשתות.

בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר 1 בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר 1 בין $\displaystyle |V|+u$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הקביל הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי, קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש, מורכב משני חלקים:

1. מסלול זהה לחלוטין למסלול קביל מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי
2. מסלול בעלות 1 ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$

לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.

Dijkstra עם העדפה למסלולים שארכם זוגי

שאלה

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

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

תשובה

נניח שזהו הגרף המקורי:

בעיית המסלול הזול ביותר.

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. כל קשת בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין $\displaystyle u$ ב$\displaystyle A$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
2. כל קשת בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.

התרשים הבא מראה זאת (רק חלק מהקשתות מצויירות).

הוספת הקשתות.

בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle 1$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle x+1$ בין $\displaystyle |V|+u$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי (כולל הקנס, אם יש), קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש, מורכב משני חלקים:

1. מסלול זהה לחלוטין למסלול מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי
2. מסלול בעלות 1 ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$, אם החלק הראשון זוגי, ומסלול בעלות $\displaystyle x+1$, אם החלק הראשון אי-זוגי.

לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם 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.

תשובה

שימו לב: אלגוריתם Dijkstra אינו פועל בצורה נכונה על גרפים בעלי קשתות שליליות (אפילו אם אין מעגל שלילי). לא למדנו אחרת, וקל לבנות דוגמה המראה זאת.

נניח שזהו הגרף המקורי:

הבעיה המקורית.

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.
2. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
3. במקום הקשת השלילית $\displaystyle (x,y)$ (בגרף המקורי), נמתח קשת מהצומת המתאים ל$\displaystyle x$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle y$ ב$\displaystyle B$ במחיר 0. התרשים הבא מראה זאת.

הוספת הקשתות.

נניח שלקשת השלילית היה מחיר $\displaystyle -z$. בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle z$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle B$, נמתח קשת במחיר 0 בין $\displaystyle u+|V|$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי, קטן בדיוק ב$\displaystyle z$ ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: בגרף המקורי, ייתכן שהמסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ לא השתמש בקשת השלילילת, וייתכן שהשתשמש בו. במקרה הראשון, תהיה קפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$, ובמקרה השני, תהיה קפיצה מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$. הקפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$ עולה $\displaystyle z$ יותר מאשר המסלול המקורי. הקפיצות מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$ גם כן עולות $\displaystyle z$ יותר מאשר המסלול המקורי, שכן עלות כל אחת משתי הקשתות היא 0, והנוסע לא קיבל את התשלום $\displaystyle z$ מהחברה.

כעת כל הקשתות אינן שליליות, ומותר להריץ את Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של Dijkstra.