מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם "הכפלת מטריצות"

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

הרעיון הכללי

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

מעניין לראות שבגרף ה"מוסף", אפשר להרחיב את משמעות ההגדרה. המשפט הבא מפרט זאת.

לפני שנוכיח את המשפט, להלן דוגמה.

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

כעת נוכיח את המשפט.

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

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

פסוודו-קוד

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

Matrix-Multiplication(G, Edge-Costs, m)
1	if m == 1
2		return Edge-Costs

3	D' = Matrix-Multiplication(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] = ∞

9			for w in V(G)
10				if D[u][v] > D'[u][w] + Edge-Costs[w][v]
11					D[u][v] = D'[u][w] + Edge-Costs[w][v]
	
12	return D

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

1	n = Length( V(G) )

2	D = Matrix-Multiplication(G, Edge-Costs, n - 1)

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

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

בתבנית:קוד בשורה, שורות 1-2 מזהות את תנאי העצירה. כפי שהוכחנו מקודם, אם $m=0$ אז המסלול הזול ביותר מ$u$ ל$v$ הוא בדיוק הכניסה ה$(u,v)$ במטריצה תבנית:קוד בשורה; לכן אנו מחזירים מטריצה זו במקרה זה.

שורה 3 מחשבת את המסלולים הזולים ביותר עבור המקרה הקצר באחת (כלומר $m-1$), ושומרת את התוצאה במטריצה זמנית תבנית:קוד בשורה. כעת 5-12 מייצרות את המטריצה עבור המרחק $m$, וממלאות אותה. נשים לב שעבור כל $u$ ו$v$ (הלולאות ב6 ו7), עוברים על כל צומת ביניים $w$ אפשרי, בדיוק כפי שראינו ברעיון הכללי.

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

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

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