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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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


כדאי לדעת:

בספר הקורס, הפרק "Single-Source Shortest Paths" (תתי פרקים 1 ו2) מכסה

נושא זה.


מימוש C++

boost::dijkstra_shortest_paths


הבעיה[עריכה]

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


שימו לב:

בדף זה לא נעסוק במחירי קשתות שאינם חיוביים.




דוגמה:

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

בעיית המסלול הזול ביותר.
בעיית המסלול הזול ביותר.

רוצים למצא את המסלול הזול ביותר מ לכל צומת אחר בגרף. המסלול הזול ביותר ל, לדוגמה, הוא , ועלותו 6.


אלגוריתם Dijkstra[עריכה]

הרעיון הכללי[עריכה]

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

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

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

  1. בתחילה נאתחל את כל איברי Min-Costs ל, למעט Min-Costs[s], שאותו נאחל ל0; נכניס את כל הצמתים לpq.
  2. כל עוד pq אינו ריק, נשלוף ממנו את הצומת u שעבורו Min-Costs[u] הקטן ביותר (מבין אלה שבpq). נעדכן את ערכי שכניו בMin-Costs.



דוגמה:

עבור הגרף שראינו לעיל, וצומת המוצא , הנה המצב ההתחלתי:

אלגוריתם Dijkstra - מצב התחלתי.
אלגוריתם Dijkstra - מצב התחלתי.

מבין כל הצמתים בpq, לצומת 1 ערך Min-Costs המינימאלי. נוציא אותו, לכן, ונעדכן את שכניו:

אלגוריתם Dijkstra - צעד 1.
אלגוריתם Dijkstra - צעד 1.

מבין כל הצמתים בpq, לצומת 2 ערך Min-Costs המינימאלי. נוציא אותו, לכן, ונעדכן את שכניו:

אלגוריתם Dijkstra - צעד 2.
אלגוריתם Dijkstra - צעד 2.

נמשיך כך הלאה עד שpq יתרוקן.


פסוודו-קוד[עריכה]

להלן הפסוודו-קוד לאלגוריתם 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] )

הנה הסבר לDijkstra:

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


שימו לב:

#קריטריון ההשוואה של pq הוא הערך של Min-Costs. כלומר, מבחינת pq, האיבר u נחשב קטן מהאיבר v אמ"ם Min-Costs[u] < Min-Costs[v].
  1. בתורי קדימויות במימוש ערימה בינארית שראינו, שינוי חיצוני של ערך אחד מאיברי תור הקדימויות הוא הרסני. הפעולה Decrease-Key מתקנת מצב זה, אלא שלא ראינו פעולה כזו במימוש שראינו. אנו נניח שפעולה זו קיימת, ושסיבוכיותה לוגריתמית.

נכונות[עריכה]

משפט:

ב12, Min-Costs מכיל את הערכים הנכונים.


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



משפט:

בתחילת האיטרציה ה של 6-11:

  1. לכל צומת v, אם Min-Costs[v] < ∞, אז יש מסלול במחיר Min-Costs[v] מs לv.
  2. אם v הוא הצומת הקטן ביותר בpq (במובן שMin-Costs[v] הוא הקטן), אז אין מסלול מs ל שמחירו קטן יותר (ממש) מMin-Costs[v].



הוכחה: (בסיס האינדוקציה) בתחילת האיטרציה הראשונה Min-Costs[s] == 0,‏ בעוד שלכל ,‏ Min-Costs[v] > 0. מכאן גם ברור שs הוא הצומת הקטן ביותר. ברור שיש מסלול מs לעצמו במחיר 0, וגם ברור שאין מסלול זול יותר מ0 (כי מחירי כל הקשתות חיוביים).

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

נניח שטענה 1 אינה נכונה, דהיינו שאין מסלול מs לv כלשהו שעלותו Min-Costs[v] < ∞. נגדיר כ את האיטרציה האחרונה שבה שונה Min-Costs[v] (ב10). עפ"י הנחת האינדוקציה, באיטרציה אכן יש מסלול מs לu במחיר Min-Costs[u] (כפי שהיה ערכו באיטרציה ), אבל עפ"י זאת, 10 קובעת את Min-Costs[v] למחיר מסלול אפשרי - המסלול מs לu שבסופו משורשרת קשת מu לv.

נניח שטענה 2 איננה נכונה, דהיינו שיש מסלול זול יותר מMin-Costs[v]. נגדיר מסלול זה כ (עבור כלשהו).

המסלול מs לv.
המסלול מs לv.

נשים לב לאבחנות הפשוטות הבאות:



  1. המסלול הזול ביותר מ לכל זול יותר מהמסלול הזול ביותר מ ל (למה?).

מהאבחנה הפשוטה הראשונה, ברור שיש צומת במסלול שאינו בpq אך הצומת שאחריו במסלול כן בpq (אם לא, כיצד ייתכן ש אינו בpq אך כן?). יש שתי אפשרויות:

באפשרות הראשונה, ,‏ (כלומר, רק בתור הקדימויות).

כולם למעט v מחוץ לpq.
כולם למעט v מחוץ לpq.

נניח שזה המצב. מהנחת האינדוקציה, היות ש כבר לא בתור הקדימויות, אז יש לו המחיר הנכון שלו. אך אם זה המצב, אז 10 בהכרח תקבע את ערכו של Min-Costs[v] למשהו שאינו גבוה ממחיר המסלול הזול ביותר מ אליו. זה סותר את את קביעתנו שטענה 2 איננה נכונה.


באפשרות השניה, נגדיר את כך ש הוא הצומת הראשון במסלול שבpq (כלומר, ).

המקרה הנותר.
המקרה הנותר.


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

ניתוח סיבוכיות[עריכה]

נניח שהגרף נתון ברשימת שכנויות. 1-2 פועלות בבירור בזמן . 3-5 מבצעת פעולות Insert, ולכן אורכות זמן במקרה הגרוע. 6-11 מבצעות פעולות Delete-Min, ולכל היותר פעולות Decrease-Key (שעפ"י הנחתנו, סיבוכיותה לוגאריתמית), ולכן הן פועלות בזמן במקרה הגרוע. הסיבוכיות, לכן, היא במקרה הגרוע.


כדאי לדעת:

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

במימוש אחר לתור קדימויות מאשר ערימה בינארית (מימוש שאותו לא נלמד בקורס).


הפרק הקודם:
חיפוש רוחבי
אלגוריתם Dijkstra
תרגילים
הפרק הבא:
מסלולים זולים לכלל הזוגות