מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Floyd-Warshall

דף זה הוא השלישי מבין שלושה דפים העוסקים באלגוריתמים למציאת המסלול הזול ביותר בגרף מכוון בין כל שני צמתים.

הרעיון הכללי

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

תבנית:מבנה תבנית

תבנית:מבנה תבנית

תבנית:שימו לב

לפי הגדרה זו, קל מאד לאפיין את המסלולים הזולים ביותר בגרף. המשפט הבא מראה זאת.

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

פסוודו-קוד

להלן הפסוודו-קוד לאלגוריתם:

Floyd-Warshall(G, Edge-Costs, m)
1	if m == 0
2		return Edge-Costs

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

4	n = Length( V(G) )

5	D = Make-Matrix(n, n)
	
6	for u in V(G)
7		for v in V(G)
8			D[u][v] = D'[u][v]

9			if D[u][v] > D'[u][m] + D'[m][v]
10				D[u][v] = D'[u][m] + D'[m][v]
	
11	return D

ולהלן דוגמה לשימוש בו:

1	n = Length( V(G) )

2	D = Floyd-Warshall(G, Edge-Costs, n)

	# Prints 2.
3	Print( D[1][2] )

	# Prints ∞.
4	Print( D[2][1] )

ניתוח סיבוכיות

ראשית, קל לראות כי 6-10 הן $\mathrm{\Theta }(n^2)$, והן למעשה קובעות את זמן הריצה של קריאה יחידה של הפונקציה. נגדיר כ$n$ את מספר צמתי הגרף, וכ$T(m)$ את זמן הריצה של תבנית:קוד בשורה. אז $T(m)=T(m-1)+\mathrm{\Theta }(n^2)$, ולכן $T(n)=\mathrm{\Theta }(n^3)$.

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס