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

ראשית נכתוב פונקציה דומה למה שהתבקשנו לעשות, 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|))$.