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

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

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

הבעיה

נתונים גרף מכוון $G=(V,E)$, טבלת עלויות לקשתות $E$, וצומת מוצא $s\in V$ כלשהו. בהינתן צומת $v\in V$ כלשהו, רוצים לדעת מהו המסלול הזול ביותר מ$s$ ל$v$.

אלגוריתם Dijkstra

הרעיון הכללי

במהלך מציאת הפתרון נחזיק שני מבני נתונים:

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

נפעל עפ"י הצעדים הבאים:

1. בתחילה נאתחל את כל איברי תבנית:קוד בשורה לתבנית:קוד בשורה, למעט תבנית:קוד בשורה, שאותו נאחל ל0; נכניס את כל הצמתים לתבנית:קוד בשורה.
2. כל עוד תבנית:קוד בשורה אינו ריק, נשלוף ממנו את הצומת תבנית:קוד בשורה שעבורו תבנית:קוד בשורה הקטן ביותר (מבין אלה שבתבנית:קוד בשורה). נעדכן את ערכי שכניו בתבנית:קוד בשורה.

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

פסוודו-קוד

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

Dijkstra(G, Edge-Costs, s)
1	pq = Make-Priority-Queue()

2	Min-Costs = Make-Array( Length(V(G)) )

3	for u in V(G)
4		Min-Costs[u] = u == s? 0 : ∞
5		Insert(pq, u)
		
6	while Size(pq) > 0
7		u = Delete-Min(pq)

8		for v in A(G, u)
9			if Min-Costs[v] > Min-Costs[u] + Edge-Costs[ (u, v) ]
10				Min-Costs[v] = Min-Costs[u] + Edge-Costs[ (u, v) ]
11				Decrease-Key(pq, v)
	                	
12	return Min-Costs

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

1	Min-Costs = Dijkstra(G, Edge-Costs, 1)

	# Prints 0.
2	Print( Min-Costs[1] )

	# Prints 6.
3	Print( Min-Costs[3] )

הנה הסבר לתבנית:קוד בשורה:

• ב1 מייצרים את את תור הקדימויות תבנית:קוד בשורה, וב2 מייצרים את את המערך תבנית:קוד בשורה.
• הלולאה 6-11 פועלת כל עוד תבנית:קוד בשורה אינו ריק.
• 7 מוציאה את האיבר הקטן בתבנית:קוד בשורה (עפ"י קריטריון ההשוואה שהזכרנו), ו-8-11 מעדכנת את שכניו.
• 11 מעדכנת את תבנית:קוד בשורה שערך אחד מאיבריו ירד.

נכונות

ההוכחה היא באינדוקציה על הטענות הבאות:

תבנית:הוכחה

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

נניח שהגרף נתון ברשימת שכנויות. 1-2 פועלות בבירור בזמן $\mathrm{\Theta }(|V|)$. 3-5 מבצעת $|V|$ פעולות תבנית:קוד בשורה, ולכן אורכות זמן $\mathrm{\Theta }(|V|\cdot \log (|V|))$ במקרה הגרוע. 6-11 מבצעות $|V|$ פעולות תבנית:קוד בשורה, ולכל היותר $|E|$ פעולות תבנית:קוד בשורה (שעפ"י הנחתנו, סיבוכיותה לוגאריתמית), ולכן הן פועלות בזמן $\mathrm{\Theta }((|V|+|E|)\cdot \log (|V|))$ במקרה הגרוע. הסיבוכיות, לכן, היא $\mathrm{\Theta }((|V|+|E|)\cdot \log (|V|))$ במקרה הגרוע.