משתמש:Galaranty/אלגוריתם דייקסטרה

ערך זה דורש ידע מוקדם. אם אתם מתקשים להבין את הערך מומלץ לעיין ב:

תבנית {{אלגוריתם}} ריקה מתוכן. יש להזין פרמטרים בערך או בוויקינתונים.

אלגוריתם דייקסטרה, פרי יצירתו של אדסחר דייקסטרה^[1], הוא אלגוריתם למציאת המסלול הקל ביותר (כלומר שסכום משקלות קשתותיו הוא המינימלי האפשרי) מקדקוד (צומת) מקור לקדקוד יעד בגרף ממושקל, או למציאת כל המסלולים הקלים ביותר בגרף מקודקוד מקור לשאר הקודקודים. לכן הוא נקרא לעיתים אלגוריתם למציאת המסלולים הקלים ממקור יחיד.

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

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

פעולת האלגוריתם

בקצרה

עבור כל קודקוד, מסומן האם ביקרו בו או לא ומה מרחקו מקודקוד המקור S. לתקן TODO

אתחול: בהתחלה כל הקודקודים מסומנים שלא ביקרו בהם, ומרחקם מוגדר כאינסוף (פרט למקור, שמרחקו מוגדר כ-0).

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

פסאודו קוד^[2]

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

function Dijkstra(Graph, Source):
    for v in Graph.Vertices:
        DistEst[v] = ∞
        Prev[v] = NIL
    DistEst[Source] = 0
    Initialize min priority queue Q, with all the graph vertices, keyed by their DistEst[v]

    while Q is not empty:
        u = Q.ExtractMin()
        for v adjacent to u:
            if DistEst[v] > DistEst[u] + Weight(u,v):
                -- a shorter path to v has been discovered!
                DistEst[v] = DistEst[u] + Weight(u,v)
                Prev[v] = u
                Q.DecreaseKey(v, DistEst[v])
    return DistEst, Prev

הפסודו קוד מוצא את המסלול הקצר ביותר מ-source לכל קודקוד בגרף. אם המטרה היא למצוא רק את המסלול הקצר ביותר מ-source לקודקוד יעד מסוים, ניתן לשנות את תנאי העצירה של הלולאה הראשית (TODO שורות) כך שיעצור לאחר שקודקוד היעד נשלף מ-Q.

דוגמת הרצה

TODO. להתחיל ממשהו מוכן מראש מויקימדיה, ולשפר למשהו שלך.

נכונות

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

נסמן ב-TrueDist[v] את המרחק הקצר ביותר מ-s ל-v. ‏ DistEstו-Prev מתייחסים למשתנים בפסודו קוד הנ"ל.

בסיס האינדוקציה:

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

צעד האינדוקציה:

נניח שביקרנו ב-k קודקודים, ולכל קודקוד האלגוריתם מצא את המסלול הקצר ביותר (הנחת האינדוקציה). נסמן ב-v את הקודקוד ה-k+1 שהאלגוריתם ביקר בו.

יהי Q מסלול כלשהו מ-s ל-v. נוכיח שמשקלו איננו קטן משל $P_{v}$ .

נסמן ב-u את Prev[v], ב-y את הקודקוד הראשון ב-Q שאיננו אחד מ-k הקודקודים הראשונים שבוקרו, וב-x את הקודקוד שלפני y במסלול Q.

בגלל שהקשת uv נשלפה מתור הקדימויות לפני xy, מתקיים $DistEst[u]+w(u\rightarrow v)\leq DistEst[x]+w(x\rightarrow y)$ (אחרת x היה נשלף מתור הקדימויות לפני u).

לפי הנחת האינדוקציה והעובדה שהאלגוריתם כבר ביקר ב-u ו-x, ניתן להציב את TrueDist במקום DistEst: $TrueDist[u]+w(u\rightarrow v)\leq TrueDist[x]+w(x\rightarrow y)$ . כלומר, אפילו תת-המסלול של Q מ-s ל-y איננו עדיף על $P_{v}$ . הוספת הקשתות הנוספות במסלול Q רק תגדיל את משקלו.

ולכן המשקל של המסלול שאלגוריתם דייקסטרה מצא קטן או שווה לכל מסלול אחר מ-s ל-v.^[3]^[4]

איור להמחשת ההוכחה. חץ מקווקו מסמן מסלול שיכול לכלול מספר קודקודים. אם אלגוריתם דייקסטרה בחר "לצאת" מ-visited עם הקשת uv, אז לא ייתכן שניתן למצוא מסלול קל יותר עם הקשת xy.^[א]^[4] TODO למחוק את הכיתוב Px ו-Pu.

קשתות שליליות

כאשר בגרף יש משקלים שליליים, לא מובטח שאלגוריתם דייקסטרה יימצא את המסלול הקצר ביותר. ^[3]

בהוכחת הנכונות הנ"ל, הביטוי $DistEst[u]+w(u\rightarrow v)\leq DistEst[x]+w(x\rightarrow y)$ איננו נכון, משום שייתכן ש-w(xy) שלילי.^[3]

דוגמה נגדית:

sa=2

sb=3

ba=-2

https://www.cs.dartmouth.edu/~deepc/LecNotes/cs31/lec17+18.pdf:

First, note that the shortest cost path from s to a is actually (s, b, a) of total cost 1. Let’s see what DIJKSTRA does. First s will assign a distance label dist[a] = 2 and dist[b] = 3. Then, it will pick a into R since dist[a] was the smaller one. And then, by design, it will never update dist[a] ever again. Remember, the reason DIJKSTRA does this is to make sure the algorithm proceeds fast. However, the negative edge (b, a) is never allowed to update dist[a] again. And thus DIJKSTRA misses out and gives the wrong answer. Again, if there were no negative edges, this won’t happen (as we just proved above).

סיבוכיות ובחירת מבנה נתונים לתור הקדימויות^[5]

ערך זה דורש ידע מוקדם. אם אתם מתקשים להבין את הערך מומלץ לעיין ב:

סיבוכיות זמן, סימון אסימפטוטי

סיבוכיות זמן

כל קודקוד מוכנס ומוצא מתור הקדימיות בדיוק פעם אחת. בגרף מכוון, כל קשת תופיעה פעם אחת בלולאת ה-for (שורה 10), ולכן כמות הקריאות ל-DecreaseKey היא לכל היותר E. לכן סיבוכיות הזמן הינה:^[5]

$O(INITIALIZE+V*EXTRACT\_MIN+E*DECREASE\_KEY)$

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


מבנה נתונים	אתחול	EXTRACT_MIN	DECREASE_KEY	סיבוכיות זמן ריצה של אלגוריתם דייסקטרה	הערות
רשימת קודקודים^[5]^[6]	-^[ב]	O(V)	O(1)	O(V^2)
ערימה בינארית^[5]	O(V)	O(logV)	O(logV)	O((V+E)logv)^[ג]
ערימת פיבונאצי^[5]^[6]	O(V)	O(logV)	O(1)	O(VlogV+E)	ניתוח לשיעורין
ערימת פיבונאצי חזקה (אנ'),^[7]^[6] תור ברודאל (אנ')^[8]^[6]^[ד]	O(V)	O(logV)	O(1)	O(VlogV+E)	סיבוכיות מקרה גרוע, ללא ניתוח לשיעורין

רשימת קודקודים הינה המימוש הפשוט ביותר.^[9] המימוש באמצעות ערימה בינארית נחשב למימוש נפוץ, בגלל האיזון בין ביצועים לפשטות מימוש.^[4]^[10]^[11]^[12]^[ה]

ערימת פיבונאצי ודומיה מצליחה לשפר את הסיבוכיות בכך שהיא מנצלת את העובדה שהאלגוריתם קורא הרבה יותר פעמים ל-DECREASE_KEY מאשר ל-EXTRACT MIN.^[5] למרות היעילות התיאורטית, בפרקטיקה נדיר לראות מימושים המתבססים על ערימות פיבונאצי (וערימות מתוחכמות אחרות), בגלל מורכבות המימוש, וייתכן שגם בגלל גורמים קבועים אשר הופכים את מבנה הנתונים לפחות יעיל ברוב המקרים המעשיים.^[3]^[7]^[11]^[6]^[ו]

סיבוכיות מקום

TODO

אופטימליות אוניברסלית

TODO

רעיון האלגוריתם

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

יהי P המסלול הקצר ביותר מקודקוד S לקודקוד T. ייתכן ש-P עובר בקודקודים רבים. עבור כל קודקוד V, החלק ממסלול P שמגיע מ-S אליו מהווה את הדרך הקצרה ביותר האפשרית להגיע מ-S ל-V. אם לא כן, ניתן היה לקצר את המסלול מ-S ל-V ובכך להקטין את המרחק הכולל מ-S ל-T, ואם כך P אינו המסלול הקצר ביותר, בסתירה להגדרתו.

עיקרון זה מאפשר לבסס את מציאת המסלול הקצר ביותר על מעין תכנון דינאמי. הפתרון לבעיה מצוי בפתרון לתת הבעיות שלה. המסלול הקצר ביותר מ-S ל-T יימצא על סמך המסלולים הקצרים ביותר מ-S לקודקודים שקדמו ל-T.

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

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

יישומים

TODO לשאול ב-stack exchange

תקשורת

ביואינפורמטיקה

השוואה לאלגוריתמים אחרים

דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים

ראו גם – אלגוריתם חיפוש לרוחב

ניתן לראות את אלגוריתם דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים.^[13]^[14] בפרט, אלגוריתם דייקסטרה שקול לאלגוריתם חיפוש לרוחב בגרף שבו כל המשקלים שווים ל-1.^[14]^[15]

סיבוכיות אלגוריתם חיפוש לרוחב היא O(V+E),^[16] בהשוואה ל-O(VlogV+E) של דייקסטרה. כלומר, בעיית המסלול הקצר ביותר בגרף לא ממושקל הינה קלה יותר מאשר בגרף ממושקל.

אלגוריתם חיפוש לרוחב יכול למצוא מסלול קצר ביותר בגרף ממושקל באופן הבא: ניצור גרף חדש, G', שבו עבור כל קשת e=uv ניצור w(e) קשתות חדשות בעלות משקל=1 המחברות את u ו-v דרך w(e)-1 "קודקודי דמה" חדשים. TODO תמונה. אך שיטה זו מגדילה משמעותית את גודל הגרף שעליו צריך לבצע חיפוש. ניתן לראות את דייקסטרה כאופטימיזציה של שיטה זו, אשר אינה דורשת הגדלה מלאכותית של הגרף.^[14]

גרפים לא מכוונים

דייקסטרה יכול לפעול בגרף לא מכוון, אך במקרה זה ניתן ליצור אלגוריתמים בעלי סיבוכית עדיפה. ישנו אלגוריתם אקראי בסיבוכיות $O(E{\sqrt {logV\cdot loglogV}})$ בסבירות גבוהה.^[17]

גרפים בעלי משקלים שליליים

ערכים מורחבים – אלגוריתם בלמן-פורד, האלגוריתם של ג'ונסון

האלגוריתם הקלאסי לבעיה זו הוא אלגוריתם בלמן-פורד. נהוג ללמוד אלגוריתם זה לצד דייקסטרה בקורסי מבוא לאלגוריתמים רבים.^[18] בלמן-פורד דומה במובנים מסוימים לדייקסטרה: גם הוא מיישם את התבנית האלגוריתמית של פורד לאלגוריתמים למציאת המסלול הקצר ביותר (ראה בפרק ההיסטוריה),^[19] וגם הוא אלגוריתם חמדן המשתמש בתכנון דינמי.^[3]

סיבוכיות הזמן של אלגוריתם בלמן-פורד היא O(VE).^[20] זו הייתה הסיבוכיות מקרה גרוע הטובה ביותר שהייתה ידועה עד ל-2023, אז פורסם אלגוריתם אקראי בעל סיבוכיות זמן של Õ(EV^8/9)^[ז] בסבירות גבוהה.^[21] כלומר, בעיית המסלול הקצר ביותר הינה קשה יותר כאשר יש בגרף משקלים שליליים.

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

שימוש ביוריסטיקות - A*

ערך מורחב – אלגוריתם חיפוש A*

ניתן לראות את אלגוריתם A* כוראיציה של דייקסטרה שמשתמשת בפונקציית יוריסטיקה כדי למצוא יותר מהר את המסלול הקצר ביותר. באלגוריתם A* נשלף הקודוקד v שממזער את DistEst[v]+h(v), כאשר h היא פונקציית יוריסטיקה האומדת את המרחק מ-v לקודקוד היעד. השוו זאת לדייקסטרה, אשר שולף את הקודקוד שממזער את DistEst[v] בלבד.^[22] A* שקול לדייקסטרה אם בוחרים את פונקציית היוריסטיקה h(x)=0.

לעומת דייקסטרה, A* נועד למצוא את המסלול הקצר ביותר בין זוג קודקודים ספציפי, בעוד שדייקסטרה מסוגל לפתור גם את בעיית כל המסלולים הקצרים ממקור יחיד.^[22]

במקרים רבים היוריסטיקה מאפשרת לאלגוריתם לנצל ידע חיצוני על הקודקודים. למשל, אם הגרף מייצג מיקומים, ניתן להשתמש במרחק האוקלידי בין v ליעד בתור פונקציית היוריסטיקה. כך אלגוריתם החיפוש יודע לוותר מראש על כיווני חיפוש מיותרים, ו"לכוון" ליעד. עם זאת, כדי להבטיח פלט נכון, ישנם הגבלות מסוימות על פונקציית היוריסטיקה (ראה בערך על האלגוריתם), ועבור קלטים מסוימים פונקציית המרחק האוקלידי לא מקיימת תנאים אלו.^[22]

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

תגובתיות לשינויים

TODO ואריציות. להזכיר גם את בעיית המסלול ה-k הכי קצר.

מקרים פרטיים של גרפים מכוונים ממושקלים

ישנם מקרים פרטיים בהם ניתן למצוא אלגוריתם בעל סיבוכיות עדיפה מדייקסטרה. למשל, עבור גרפים מכוונים בעלי משקלים טבעיים ידוע על אלגוריתם בעל סיבוכיות של (O(E+Vloglog(min{V,C})^[23] או O(EloglogC)^[24] כאשר C הוא המשקל המקסימלי. ישנם גם שיפורים עבור קלט גיאומטרי, גרפים מישוריים וגרפים עם משקלים אקראיים.^[25]

מערכות ניווט מודרניות

TODO

בטבע

ניתן לחשוב על בעיה זו באמצעות האנלוגיה הפיזיקלית הבאה: מתחילים להזרים מים לרשת תעלות (נניח שכל התעלות בעלות קיבולת זהה, ואין הבדלי גבהים). המים יבקרו בקודקודים באותו סדר שדייקסטרה מבקר בהם, וימצאו אותם מסלולים קצרים.^[13]^[26] TODO המחשה ויזואלית. TODO לשקול למחוק.

היסטוריה

המצאת האלגוריתם

המחקר המתמטי המודרני על מציאת המסלול הקל ביותר בגרף החל ב-TODO.

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

פורד (1956): תבנית לאלגוריתמים למציאת המסלול הקל ביותר

ראו גם – אלגוריתם בלמן-פורד (על שמו של פורד)

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

התבנית של פורד:

נסמן ב- $d(v)$ פונקציה המחזירה את הערכת המרחק מצומת המקור $s$ לכל צומת אחרת $v$ (בדומה ל-DistEst בפסודו-קוד בתחילת הערך).

אתחול: קבע $d(s)=0$ ו- $d(v)=\infty$ לכל $v\neq s$ .

לולאה: באופן איטרטיבי, בחר קשת $uv$ המקיימת $d(v)>d(u)+w(uv)$ , וקבע $d(v):=d(u)+w(u,v)$ .

פורד לא ציין אף כלל לבחירת הקשת $uv$ . אלגוריתם דייקסטרה בוחר את הקשת $uv$ שממזערת את $d(u)$ .^[19]^[27]

אדסחר דייסקטרה (1956\1959)

ראו גם – אדסחר דייקסטרה

דייסקטרה תכנן את האלגוריתם ב-1956, במטרה להציג את יכולות המחשב ARMAC (הו') בטקס החניכה החגיגי שלו. דייסקטרה רצה לבחור בעיה אלגוריתמית שגם קהל לא מתמטי יוכל להבין. הבעיה שבחר בה הייתה מציאת המסלול הקצר ביותר בין ערים הולנדיות.^[ח] דייסקטרה מספר שהוא תכנן את האלגוריתם בכ-20 דקות, בזמן הפסקת קפה שלקח כשעשה קניות עם ארוסתו. דייסקטרה האמין שדווקא משום שלא יכל להשתמש בעפרון ונייר, הוא אולץ לחשוב על אלגוריתם פשוט ואלגנטי.^[28]

דייסקטרה פירסם את האלגוריתם רק כ-3 שנים לאחר המצאתו, ב-1959. תיאור האלגוריתם התפרס על פני עמוד אחד בלבד, מתוך מאמר בן 2.5 עמודים שכלל גם תיאור של אלגוריתם גרפי נוסף.^[29] המאמר לא עסק בבחירת מימוש לתור הקדימויות (למעשה דייקסטרא כלל לא השתמש במונח),^[29] ולכן בטקסטים מודרניים לעיתים מתייחסים לסיבוכיות הזמן של האלגוריתם המקורי כ- $O(n^{2})$ .^[19]

דייסקטרה אמר שב-1956 "אלגוריתם למציאת המסלול הקצר ביותר בקושי נחשב למתמטיקה: הרי יש מספר סופי של מסלולים מ-A ל-B וברור שאחד מהם הוא הקצר ביותר, אז על מה כל המהומה?". דייקסטרא החליט לפרסם מאמר על האלגוריתם 3 שנים לאחר המצאתו, כאשר עורך של כתב עת חדש, שעסק גם בנושאים שכיום ייחשבו כחלק ממדעי המחשב,^[30] פנה לדייסקטרה ושאל אם יש לו מה לתרום לכתב העת.^[28]

בתחילת שנות השישים דייסקטרה נתקל לראשונה בטקסט שקורא לאלגוריתם על שמו, בספר לימוד גרמני.^[28]

מאמרים שפורסמו במקביל

במקביל לדייקסטרה, חוקרים אחרים פיתחו את האלגוריתם ופרסמו אותו.

ב-1957 התפרסם תיאור של האלגוריתם במאמר של חוקרים ממכון CASE (אנ').^[19] מוטיביצה-TODO

ב-1960 רייטינג והילייר פרסמו מאמר נוסף שתיאר את האלגוריתם.^[31]^[32]^[33] מוטיביצה-TODO

LEO 1 ו-British Railways (1955-1956)

LEO 1 היה מחשב בריטי שהחל לפעול ב-1951. המחשב היה שייך לתאגיד המזון J. Lyons and Co., שגם השכיר את שירותי המחשוב לגורמים אחרים. ב-1955 British Railways שכרו את שירותי המחשוב לטובת חישוב המרחק בין תחנות הרכבת שלהם. בניסוח גרפי, זוהי הבעיה של מציאת המסלול הקצר ביותר בין כל זוג קודקודים. על הבעיה עבד רוג'ר קולמן, תחת ניהולו של דייויד קמינר.

כחלק מפיתרון הבעיה, פותח אלגוריתם שאפשר להחשיב כואריציה פרימיטיבית על אלגוריתם דייסקטרה. עם זאת, האלגוריתם של קולמן כלל הרבה התאמות לבעיה הספציפית של British Railways. בנוסף, האלגוריתם מעולם לא פורסם, והידע שלנו עליו מתבסס על ריאיונות שחובבי היסטוריית מחשוב ערכו עם קולמן בשנות האלפיים. קולמן לא המשיך לעסוק במדעי המחשב, ועד לאותם ריאיונות הוא לא ידע על קיומו של האלגוריתם של דייסקטרה ועל החשיבות ההיסטורית של המצאתו שלו.^[34]^[35]

מחקר מתקדם על אופטימיזציה

https://sci-hub.se/10.1109/dt.2019.8813457

ראו גם

בעיית המסלול הארוך ביותר

קישורים חיצוניים

מצגת הסבר - אלגוריתם דייקסטרה

מדיה וקבצים בנושא Galaranty/אלגוריתם דייקסטרה בוויקישיתוף

String Module Error: Target string is empty.html Galaranty/אלגוריתם דייקסטרה, באתר MathWorld (באנגלית)

הערות שוליים

^ Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.
^ מבוסס על Cormen et al 4th edition, עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.
^ ¹ ² ³ ⁴ ⁵ קמפוס IL
^ ¹ ² ³ קליינברג וטרדוש
^ ¹ ² ³ ⁴ ⁵ ⁶ קורמן עמ' 623-624
^ ¹ ² ³ ⁴ ⁵ Michal Mrena, Peter Sedlacek, Miroslav Kvassay, Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths, IEEE, 2019-06, עמ' 335–344 doi: 10.1109/DT.2019.8813457
^ ¹ ² Strict Fibonacci Heaps 2012 Tarjan et al
^ Worst-Case E�cient Priority Queues 1996 Brodal
^ Dasgupta-Papadimitriou-Vazirani פרק 4.5
^ Chen, M., Chowdhury, R. A., Ramachandran, V., Roche, D. L., & Tong, L. (2007). Priority queues and Dijkstra's algorithm.‏
^ ¹ ² Rhyd Lewis, A Comparison of Dijkstra’s Algorithm Using Fibonacci Heaps, Binary Heaps, and Self-Balancing Binary Trees
^ נמצא בשימוש למשל בספריה הפופולארית networkx. הספריה הפופולארית והיעלה boost משתמשת בערימה d-ארית עבור d=4 (ראה קוד מקור), שהיא מעין הכללה של ערימה בינארית שאינה משפיעה באמת על הסיבוכיות (כאשר מתייחסים ל-d כקבוע).
^ ¹ ² קורמן ושות', עמ' 620
^ ¹ ² ³ Dasgupta-Papadimitriou-Vazirani פרק 4.4
^ Shaull (https://cs.stackexchange.com/users/6890/shaull), Is Dijkstra's algorithm just BFS with a priority queue?, URL (version: 2013-02-24): https://cs.stackexchange.com/q/10048
^ קורמן ושות', עמ' 558
^ Ran Duan, Jiayi Mao, Xinkai Shu, Longhui Yin, A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2023-11-06, עמ' 484–492 doi: 10.1109/focs57990.2023.00035
^ קורמן, קמפוס, קליינברג וטרדוס, פדימטטרו, וכו'
^ ¹ ² ³ ⁴ Alexander Schrijver, On the history of the shortest path problem, Documenta Mathematica Series: Optimization Stories, 2012, עמ' 155-167 doi: 10.4171/DMS/6/19 (באנגלית)
^ קורמן ושות' פרק 22.1
^ Jeremy T. Fineman, Single-Source Shortest Paths with Negative Real Weights in Õ(𝑚𝑛8/9) Time, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Association for Computing Machinery, 2024-06-11, עמ' 3–14 doi: 10.1145/3618260.3649614
^ ¹ ² ³ Dijkstra's single-source shortest path algorithm, אוניברסיטת קורנל, ‏2019 (באנגלית)
^ Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, Special Issue on STOC 2003 69, 2004-11-01, עמ' 330–353 doi: 10.1016/j.jcss.2004.04.003
^ Rolf G. Karlsson, Patricio V. Poblete, An O(mlog logD) algorithm for shortest paths, Discrete Applied Mathematics 6, 1983-05-01, עמ' 91–93 doi: 10.1016/0166-218X(83)90104-X
^ Seth Pettie, Vijaya Ramachandran, A Shortest Path Algorithm for Real-Weighted Undirected Graphs, SIAM Journal on Computing 34, 2005-01, עמ' 1431 doi: 10.1137/S0097539702419650
^ MOOCs by OUIL (2021-10-18), הרצת האלגוריתם, נבדק ב-2024-12-27
^ L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, 1956.
^ ¹ ² ³ Philip L. Frana, Thomas J. Misa, An interview with Edsger W. Dijkstra, Communications of the ACM 53, 2010-08, עמ' 41–47 doi: 10.1145/1787234.1787249
^ ¹ ² E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959-12-01, עמ' 269–271 doi: 10.1007/BF01386390
^ Numerische Mathematik, The European Digital Mathematics Library
^ P. D. Whiting, J. A. Hillier, A Method for Finding the Shortest Route Through a Road Network, OR 11, 1960, עמ' 37–40 doi: 10.2307/3007178
^ Paola Festa, Shortest Path Algorithms, Boston, MA: Springer US, 2006, עמ' 185–210, ISBN 978-0-387-30165-5. (באנגלית)
^ Stuart E. Dreyfus, An Appraisal of Some Shortest-Path Algorithms, Operations Research 17, 1969-06, עמ' 395–412 doi: 10.1287/opre.17.3.395
^ Tim Greening-Jackson, LEO I and the BR job, Self published, 2012 (באנגלית)
^ הרצאה של ג'ון גרהאם-קמינגס ב-Strata Conference London 2012, הרצאה בערוץ "O'Reilly", באתר יוטיוב (אורך: 18:24), 2 באוקטובר 2012

ביאורים

^ האיור מספק אינטואיציה, אך ישנם מקרים שבהם הוא איננו מדויק: ייתכן ש-x=u, y=v או שיש חפיפה בין הקודקודים s,u,x. בנוסף ייתכן שבמסלול מ-y ל-v יש קודקודים נוספים מבין הקודקודים שבוקרו.
^ ניתן להניח שבקלט יש רשימת קודקודים.
^ במקרה הטיפוסי, מתקיים $E=\omega(V)$, ולכן הסיבוכיות היא $O(ElogV)$.
^ תור ברודאל היה מבנה הנתונים הראשון שהתגלה בעל סיבוכיות-מקרה-גרוע השקולה לסיבוכיות לשיעורין של ערימות פיבונאצ'י. אך מבנה הנתונים היה מורכב והתבסס על מערכים דינאמיים. ערימות פיבונאצ'י חזקות נוצרו במטרה להיות מבנה נתונים פשוט יותר מתור ברודאל, אך בעל סיבוכיות זהה. (Strict Fibonacci heaps, טרחאן וברודאל ועוד מישהו, 2012) TODO במאמר הנל בסוף ה-intro מוזכרים מבני נתונים נוספים אשר זהים לערימת פיבונאצ'י חזקה פרט לפעולת meld. האם הסיבוכיות שלהם עבור דייקסטרא זהה לשל ערימות פיבונאצ'י חזקה? אם כן,יש להזכירן
^ אם הגרף מאוד צפוץ (אם לא מתקיים E=o(V^2/logV)), היעילות של המימוש הנאיבי (באמצעות מערך) בעלת סיבוכיות נמוכה יותר. אך זה לא נחשב למקרה הנפוץ. (קורמן ושות' עמ' 623)
^ במקרים רבים שבהם גודל הקלט מספיק גדול כדי לראות את היתרון של ערימות פיבונאצי, סביר שהמממש יעדיף להשתמש בגישה אלגוריתמית שונה המותאמת יותר לנתוני עתק, כמו למשל אלגוריתמי קירוב.
^ משמעות הסימון Õ (אנ') היא O כאשר מתייחסים לגורמים לוגריתמיים כזניחים. כלומר $f(n)\in {\tilde {O}}(g(n))$ הוא כתיב מקוצר של $\exists k:f(n)\in O(g(n)\log ^{k}n)$ (קורמן ושות', עמ' 73-74)
^ הגרף הכיל 64 קודקודים, שכל אחד מהם מייצג עיר בהולנד.

[1] Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.

[2] מבוסס על Cormen et al 4th edition, עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.

[:5-3] ¹ ² ³ ⁴ ⁵ קמפוס IL

[:0-4] ¹ ² ³ קליינברג וטרדוש

[:4-6] ¹ ² ³ ⁴ ⁵ ⁶ קורמן עמ' 623-624

[:7-7] ¹ ² ³ ⁴ ⁵ Michal Mrena, Peter Sedlacek, Miroslav Kvassay, Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths, IEEE, 2019-06, עמ' 335–344 doi: 10.1109/DT.2019.8813457

[:8-10] ¹ ² Strict Fibonacci Heaps 2012 Tarjan et al

[11] Worst-Case E�cient Priority Queues 1996 Brodal

[13] Dasgupta-Papadimitriou-Vazirani פרק 4.5

[14] Chen, M., Chowdhury, R. A., Ramachandran, V., Roche, D. L., & Tong, L. (2007). Priority queues and Dijkstra's algorithm.‏

[:6-15] ¹ ² Rhyd Lewis, A Comparison of Dijkstra’s Algorithm Using Fibonacci Heaps, Binary Heaps, and Self-Balancing Binary Trees

[16] נמצא בשימוש למשל בספריה הפופולארית networkx. הספריה הפופולארית והיעלה boost משתמשת בערימה d-ארית עבור d=4 (ראה קוד מקור), שהיא מעין הכללה של ערימה בינארית שאינה משפיעה באמת על הסיבוכיות (כאשר מתייחסים ל-d כקבוע).

[:9-19] ¹ ² קורמן ושות', עמ' 620

[:10-20] ¹ ² ³ Dasgupta-Papadimitriou-Vazirani פרק 4.4

[21] Shaull (https://cs.stackexchange.com/users/6890/shaull), Is Dijkstra's algorithm just BFS with a priority queue?, URL (version: 2013-02-24): https://cs.stackexchange.com/q/10048

[22] קורמן ושות', עמ' 558

[:11-23] Ran Duan, Jiayi Mao, Xinkai Shu, Longhui Yin, A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2023-11-06, עמ' 484–492 doi: 10.1109/focs57990.2023.00035

[24] קורמן, קמפוס, קליינברג וטרדוס, פדימטטרו, וכו'

[:1-25] ¹ ² ³ ⁴ Alexander Schrijver, On the history of the shortest path problem, Documenta Mathematica Series: Optimization Stories, 2012, עמ' 155-167 doi: 10.4171/DMS/6/19 (באנגלית)

[26] קורמן ושות' פרק 22.1

[28] Jeremy T. Fineman, Single-Source Shortest Paths with Negative Real Weights in Õ(𝑚𝑛8/9) Time, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Association for Computing Machinery, 2024-06-11, עמ' 3–14 doi: 10.1145/3618260.3649614

[:12-29] ¹ ² ³ Dijkstra's single-source shortest path algorithm, אוניברסיטת קורנל, ‏2019 (באנגלית)

[30] Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, Special Issue on STOC 2003 69, 2004-11-01, עמ' 330–353 doi: 10.1016/j.jcss.2004.04.003

[31] Rolf G. Karlsson, Patricio V. Poblete, An O(mlog logD) algorithm for shortest paths, Discrete Applied Mathematics 6, 1983-05-01, עמ' 91–93 doi: 10.1016/0166-218X(83)90104-X

[32] Seth Pettie, Vijaya Ramachandran, A Shortest Path Algorithm for Real-Weighted Undirected Graphs, SIAM Journal on Computing 34, 2005-01, עמ' 1431 doi: 10.1137/S0097539702419650

[33] MOOCs by OUIL (2021-10-18), הרצת האלגוריתם, נבדק ב-2024-12-27

[34] L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, 1956.

[:2-36] ¹ ² ³ Philip L. Frana, Thomas J. Misa, An interview with Edsger W. Dijkstra, Communications of the ACM 53, 2010-08, עמ' 41–47 doi: 10.1145/1787234.1787249

[:3-37] ¹ ² E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959-12-01, עמ' 269–271 doi: 10.1007/BF01386390

[38] Numerische Mathematik, The European Digital Mathematics Library

[39] P. D. Whiting, J. A. Hillier, A Method for Finding the Shortest Route Through a Road Network, OR 11, 1960, עמ' 37–40 doi: 10.2307/3007178

[40] Paola Festa, Shortest Path Algorithms, Boston, MA: Springer US, 2006, עמ' 185–210, ISBN 978-0-387-30165-5. (באנגלית)

[41] Stuart E. Dreyfus, An Appraisal of Some Shortest-Path Algorithms, Operations Research 17, 1969-06, עמ' 395–412 doi: 10.1287/opre.17.3.395

[42] Tim Greening-Jackson, LEO I and the BR job, Self published, 2012 (באנגלית)

[43] הרצאה של ג'ון גרהאם-קמינגס ב-Strata Conference London 2012, הרצאה בערוץ "O'Reilly", באתר יוטיוב (אורך: 18:24), 2 באוקטובר 2012

[5] האיור מספק אינטואיציה, אך ישנם מקרים שבהם הוא איננו מדויק: ייתכן ש-x=u, y=v או שיש חפיפה בין הקודקודים s,u,x. בנוסף ייתכן שבמסלול מ-y ל-v יש קודקודים נוספים מבין הקודקודים שבוקרו.

[8] ניתן להניח שבקלט יש רשימת קודקודים.

[9] במקרה הטיפוסי, מתקיים $E=\omega(V)$, ולכן הסיבוכיות היא $O(ElogV)$.

[12] תור ברודאל היה מבנה הנתונים הראשון שהתגלה בעל סיבוכיות-מקרה-גרוע השקולה לסיבוכיות לשיעורין של ערימות פיבונאצ'י. אך מבנה הנתונים היה מורכב והתבסס על מערכים דינאמיים. ערימות פיבונאצ'י חזקות נוצרו במטרה להיות מבנה נתונים פשוט יותר מתור ברודאל, אך בעל סיבוכיות זהה. (Strict Fibonacci heaps, טרחאן וברודאל ועוד מישהו, 2012) TODO במאמר הנל בסוף ה-intro מוזכרים מבני נתונים נוספים אשר זהים לערימת פיבונאצ'י חזקה פרט לפעולת meld. האם הסיבוכיות שלהם עבור דייקסטרא זהה לשל ערימות פיבונאצ'י חזקה? אם כן,יש להזכירן

[17] אם הגרף מאוד צפוץ (אם לא מתקיים E=o(V^2/logV)), היעילות של המימוש הנאיבי (באמצעות מערך) בעלת סיבוכיות נמוכה יותר. אך זה לא נחשב למקרה הנפוץ. (קורמן ושות' עמ' 623)

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

[27] משמעות הסימון Õ (אנ') היא O כאשר מתייחסים לגורמים לוגריתמיים כזניחים. כלומר $f(n)\in {\tilde {O}}(g(n))$ הוא כתיב מקוצר של $\exists k:f(n)\in O(g(n)\log ^{k}n)$ (קורמן ושות', עמ' 73-74)

[35] הגרף הכיל 64 קודקודים, שכל אחד מהם מייצג עיר בהולנד.

[1]

[2]

[3]

[4]

[א]

[5]

[6]

[ב]

[ג]

[7]

[8]

[ד]

[9]

[10]

[11]

[12]

[ה]

[ו]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[ז]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[ח]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

פעולת האלגוריתם

בקצרה

פסאודו קוד[2]

דוגמת הרצה

נכונות

קשתות שליליות

סיבוכיות ובחירת מבנה נתונים לתור הקדימויות[5]

סיבוכיות זמן

סיבוכיות מקום

אופטימליות אוניברסלית

רעיון האלגוריתם

יישומים

תקשורת

ביואינפורמטיקה

השוואה לאלגוריתמים אחרים

דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים

גרפים לא מכוונים

גרפים בעלי משקלים שליליים

שימוש ביוריסטיקות - A*

תגובתיות לשינויים

מקרים פרטיים של גרפים מכוונים ממושקלים

מערכות ניווט מודרניות

בטבע

היסטוריה

המצאת האלגוריתם

פורד (1956): תבנית לאלגוריתמים למציאת המסלול הקל ביותר

אדסחר דייסקטרה (1956\1959)

מאמרים שפורסמו במקביל

LEO 1 ו-British Railways (1955-1956)

מחקר מתקדם על אופטימיזציה

ראו גם

קישורים חיצוניים

הערות שוליים

ביאורים

פסאודו קוד^[2]

סיבוכיות ובחירת מבנה נתונים לתור הקדימויות^[5]