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

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

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

מימוש C++ boost::floyd_warshall_all_pairs_shortest_paths

הרעיון הכללי

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

הגדרה: נניח מסלול $\displaystyle P$ מ$\displaystyle u$ ל$\displaystyle v$:‏ $\displaystyle P=u\rightarrow w_{1}\rightarrow \cdots \rightarrow w_{i}\rightarrow v$ נאמר שהקבוצה $\displaystyle \left\{w_{1},\ldots ,w_{i}\right\}$ היא קבוצת צמתי הביניים של המסלול $\displaystyle P$.

שימו לב: להלן נקודה שמבלבלת חלק מהסטודנטים מדי שנה. אנו עוסקים בגרפים בהם הצמתים הם מספרים שלמים. לכן, כל אחד מ$\displaystyle \left\{u,w_{1},\ldots ,v\right\}$ הוא פשוט מספר שלם מהקבוצה $\displaystyle \left\{1,\ldots ,\vert V\vert |\right\}$.

דוגמה: להלן הגרף המקורי לבעיה: בעיית המסלולים הזוגים לכלל הזוגות. (נזכר שהגרף ה"מוסף" נוצר על ידי הוספת קשתות במחירים 0 ואינסוף.) במסלול $\displaystyle 1\rightarrow 3\rightarrow 2$, קבוצת צמתי הביניים היא $\displaystyle \left\{3\right\}$. במסלול $\displaystyle 1\rightarrow 3\rightarrow 4\rightarrow 2$, קבוצת צמתי הביניים היא $\displaystyle \left\{3,4\right\}$. במסלול $\displaystyle 1\rightarrow 2$, קבוצת צמתי הביניים היא $\displaystyle \left\{\right\}$ (הקבוצה הריקה). במסלול $\displaystyle 1\rightarrow 2\rightarrow 2\rightarrow 2\rightarrow 2$, קבוצת צמתי הביניים היא $\displaystyle \left\{2\right\}$.

הגדרה: נגדיר כ$\displaystyle d^{(m)}(u,v)$ את מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ מבין אלה שכל צומת ביניים שלהם שייך ל$\displaystyle \{1,...,m\}$. במילים אחרות, $\displaystyle d^{(m)}(u,v)$ הוא מחיר המסלול הזול ביותר מבין אלה מהצורה $\displaystyle u\rightarrow w_{1}\rightarrow ...\rightarrow w_{k}\rightarrow v,$ כשכל $\displaystyle w_{i}$ שייך ל$\displaystyle \{1,\ldots ,m\}$.

שימו לב: גם באלגוריתם "הכפלת מטריצות" הגדרנו $\displaystyle d^{(m)}(u,v)$. אין קשר בין ההגדרה כאן להגדרה שם.

דוגמה: בגרף שראינו, שני מסלולים (מתוך מספר מסלולים) מ$\displaystyle 1$ ל$\displaystyle 2$: המסלול $\displaystyle 1\rightarrow 2$ שעלותו $\displaystyle 5$, ושאינו עובר דרך אף צומת ביניים. המסלול $\displaystyle 1\rightarrow 4\rightarrow 2$ שעלותו $\displaystyle 2$, ושעובר דרך צומת הביניים $\displaystyle 4$. קל לראות, לכן: $\displaystyle d^{(0)}(1,2)=d^{(1)}(1,2)=d^{(2)}(1,2)=d^{(3)}(1,2)=5$ $\displaystyle d^{(4)}(1,2)=2$

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

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

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

משפט: $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=0$. $\displaystyle min\{d^{(m-1)}(u,v),d^{(m-1)}(u,m)+d^{(m-1)}(m,v)\}$, אם $\displaystyle m>1$.

הוכחה: נזכר ש$\displaystyle d^{(m)}(u,v)$ משמעו המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ שכל אחד מצמתי הביניים שלו לקוח מהקבוצה $\displaystyle \left\{1,\ldots ,m\right\}$

אם $\displaystyle m=0$, אז $\displaystyle d^{(m)}(u,v)$ אינו כולל צמתי ביניים. מדובר לכן במחיר הזול ביותר הישיר מ$\displaystyle u$ ל$\displaystyle v$.

אם $\displaystyle m>0$, אז יש שתי אפשרויות:

1. $\displaystyle m$ אינו מופיע בקבוצת צמתי הביניים (כלומר, המסלול הזול ביותר אינו עובר דרך $\displaystyle m$).
2. $\displaystyle m$ מופיע בקבוצת צמתי הביניים (כלומר, המסלול הזול ביותר אכן עובר דרך $\displaystyle m$).

במקרה הראשון, היות שלא משתמשים ב$\displaystyle m$, אז מדובר במסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ שכל אחד מצמתי הביניים שלו לקוח מהקבוצה $\displaystyle \left\{1,\ldots ,m-1\right\}$, כלומר התשובה היא פשוט $\displaystyle d^{(m-1)}(u,v)$.

במקרה השני, היות שמשתמשים ב$\displaystyle m$, המסלול מתחלק לשני חלקים:

• מ$\displaystyle u$ ל$\displaystyle m$. בחלק זה אפשר להניח ש$\displaystyle m$ אינו צומת ביניים (מדוע?). בקטע זה, לכן, התשובה היא פשוט $\displaystyle d^{(m-1)}(u,m)$.
• מ$\displaystyle m$ ל$\displaystyle v$. גם בחלק זה אפשר להניח ש$\displaystyle m$ אינו צומת ביניים (מדוע?). גם בקטע זה, לכן, התשובה היא פשוט $\displaystyle d^{(m-1)}(u,m)$.

פסוודו-קוד

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

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 הן $\displaystyle \Theta (n^{2})$, והן למעשה קובעות את זמן הריצה של קריאה יחידה של הפונקציה. נגדיר כ$\displaystyle n$ את מספר צמתי הגרף, וכ$\displaystyle T(m)$ את זמן הריצה של Floyd-Warshall(G, Edge-Costs, m). אז $\displaystyle T(m)=T(m-1)+\Theta (n^{2})$, ולכן $\displaystyle T(n)=\Theta (n^{3})$.

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

אלגוריתם Floyd-Warshall

הפרק הבא: זרימה - הגדרות