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

רעיון משותף

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

נשנה את הפסוודו-קוד כך שיחזיר גם מטריצה $\displaystyle P$ אשר מכילה בכניסה ה[u][v] את צומת $\displaystyle w$ זה.
נשתמש בפונקציה הבאה, אשר מקבלת מטריצה $\displaystyle P$ זו ושני צמתים, ומשתמשת בצמתי הביניים כדי

להדפיס את צמתי הביניים של המסלול ביניהם. (בכל אחד משני הסעיפים יהיה ברור ש $\displaystyle P$ למעשה מתארת את המסלול הזול ביותר, ולכן היא נקראת כאן Min-Costs-Path.)

Cheapest-Path(Min-Costs-Path, u, v)
1	w = Min-Costs-Path[u][v]

2	if w == u or w == v
3		return

4	Cheapest-Path(Min-Costs-Path, u, w)

5	print w

6	Cheapest-Path(Min-Costs-Path, w, v)

אלגוריתם "הכפלת מטריצות"

Matrix-Multiplication(G, Edge-Costs, m)
1	P = Make-Matrix(n, n)

2	if m == 1
3		for u in V(G)
4			for v in V(G)
5				P[u][v] = v		

6		return (Edge-Costs, P)
	
7	D' = Matrix-Multiplication(G, Edge-Costs, m - 1)
	
8	n = Length( V(G) )
	
9	D = Make-Matrix(n, n)
		
10	for u in V(G)
11		for v in V(G)
12			D[u][v] = &infin;
	
13			for w in V(G)
14				if D[u][v] > D'[u][w] + Edge-Costs[w][v]
15					D[u][v] = D'[u][w] + Edge-Costs[w][v]
16					P[u][v] = w

17	return (D, P)

אלגוריתם Floyd-Warshall

Floyd-Warshall(G, Edge-Costs, m)
1	P = Make-Matrix(n, n)

2	if m == 0
3		for u in V(G)
4			for v in V(G)
5				P[u][v] = v		

6		return (Edge-Costs, P)

7	D' = Floyd-Warshall(G, Edge-Costs, m - 1)

8	n = Length( V(G) )

9	D = Make-Matrix(n, n)

10	for u in V(G)
11		for v in V(G)
12			D[u][v] = D'[u][v]

13			if D[u][v] > D'[u][m] + D'[m][v]
14				D[u][v] = D'[u][m] + D'[m][v]
15				P[u][v] = m

16	return (D, P)