אלגוריתם דייקסטרה

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

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

בגרף המייצג רשת כבישים, המסלול האופטמיאלי הוא הדרך המהירה ביותר להגיע ממקום למקום. ברשתות תקשורת, אלגוריתם דייקסטרה משמש בפרוטוקולי ניתוב למציאת מסלולי תקשורת אופטימליים (למשל Open Shortest Path First).

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

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

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

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

בביטויי סיבוכיות, הביטויים E ו-V מתייחסים לגודל קבוצת הקודקודים והקשתות, ולא לקבוצות עצמן. למשל, O(V+E) הוא כתיב מקוצר של O(|V|+|E|).

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

הפסודו קוד מוצא את המסלול הקצר ביותר מהמקור לכל קודקוד בגרף. אם המטרה היא למצוא רק את המסלול הקצר ביותר ממקור ליעד מסוים, ניתן לשנות את תנאי העצירה של הלולאה הראשית כך שיעצור לאחר שקודקוד היעד נשלף מ-Q.function Dijkstra(Graph, Source):
    for v in Graph.Vertices:
        DistEst[v] = ∞
        Prev[v] = NIL
    DistEst[Source] = 0
    Initialize min priority queue Q, with all 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מבוסס על Cormen et al. (2022), עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.

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

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

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

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

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

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

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

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

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

 דוגמת הרצה 
ללא|מסגרת|דוגמת הרצה של דייקסטרה מהמקור a ליעד b.המספר הכחול מעל לקודקוד מייצג את הערכת המרחק מהמקור (DistEst).

 אינטואיציה 
דייקסטרה מגלה את המסלול הקל ביותר תחילה מהקודקודים הקרובים ביותר למקור, ולאחר מכן מקודקודים רחוקים יותר ויותר. למשל, בדוגמת ההרצה הנ"ל תחילה מתגלה המסלול מקודקוד שמרחקו מהמקור הוא 7, לאחר מכן 9, וכו'.Mehlhorn & Sanders (2008), עמ' 198

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

 תכונות 
 האלגוריתם מוצא עץ מסלולים מזעריים . זהו תת-גרף שהוא עץ שמושרש בקודקוד המקור, וכל מסלול מהשורש לכל קודקוד אחר הוא מסלול קל ביותר בגרף המקורי. אם הגרף קשיר, זהו עץ פורש.Cormen et al. (2022), עמ' 608
 סיבוכיות מקום: סיבוכיות המקום היא O(|V|), הנדרשים עבור תור הקדימויות Q והמילון DistEst.
 אם אין מסלול מהמקור לקודקוד מסוים v, יתקיים DistEst[v]=inf ו-Prev[v]=nil.
 הערכת המרחק תמיד גדולה או שווה למרחק האמיתי.Cormen et al. (2022), עמ' 611

 חמדנות ותכנון דינמי 

מאחר שכל מסלול קל ביותר מכיל תת-מסלולים שגם הם מסלולים קלים, לבעיה יש . כלומר, הפתרון יכול להבנות מפתרון בעיות קטנות יותר. בעיות מסוג זה מתאימות לפתרון בעזרת אלגוריתמים חמדניים ותכנון דינמי.Cormen et al. (2022), עמ' 605-606 החמדנות של האלגוריתם באה לידי ביטוי בכך שהאלגוריתם בוחר את הקודקוד שנראה בשלב הנוכחי כקרוב ביותר. ניתן לראות את הגישה החמדנית כפתרון יעיל של בעיית תכנון דינמי.

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

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

כמו בפסאודו קוד הנ"ל, נסמן ב-DistEst[v] את הערכת המרחק מ-s ל-v. בנוסף, נסמן ב-TrueDist[v] את המרחק הקל ביותר מ-s ל-v.

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

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

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

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

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

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

נסמן ב-u את הקודקוד שקודם ל-v במסלול הקל ביותר שהאלגוריתם מצא עד כה (Prev[v] בפסאודו קוד הנ"ל). בנוסף נסמן ב-y את הקודקוד הראשון ב-Q שאיננו אחד מ-k הקודקודים הראשונים שנשלפו, וב-x את הקודקוד שלפני y במסלול Q.

בגלל שהקשת uv נשלפה מתור הקדימויות לפני xy, מתקיים  (במילים: הערכת המשקלים של המסלול P קטנה או שווה להערכת המשקל של המסלול Q). אחרת x היה נשלף מתור הקדימויות לפני u.

לפי הנחת האינדוקציה והעובדה שהאלגוריתם כבר ביקר ב-u ו-x, ניתן להציב את TrueDist במקום DistEst: . כלומר, אפילו תת-המסלול של Q מ-s ל-y איננו עדיף על . הוספת הקשתות הנוספות במסלול Q רק יכולה להגדיל את המשקל.

ולכן המשקל של המסלול שאלגוריתם דייקסטרה מצא קטן או שווה לכל מסלול אחר מ-s ל-v.. ישנה מהדורה מתורגמת: פיתוח אלגוריתמים, בתרגום תמר אלמוג, 2010, הוצאת האוניברסיטה הפתוחה.
ללא|איור להמחשת ההוכחה.

המסלול הקצר ביותר שדייקסטרה מצא, P, מסומן בירוק. המסלול האדום הוא מסלול אלטרנטיבי, Q.

חץ שבור מסמן תת-מסלול. באליפסה הכחלחלה יש את הקודקודים שהוצאו מהתור.

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

|מסגרת

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

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

כפי שניתן לראות בדוגמה, יכול להיות מסלול בו קשת חיובית כבדה ש"מחביאה" מדייקסטרה שאחריה יש קשתות שליליות, שיכולות לקזז את הקשת הכבדה, ואף להפוך את המסלול לקל ביותר.
מרכז|ממוזער|דוגמה לגרף בעל משקלות שליליות, שבו דייקסטרה לא יצליח למצוא את המסלול הקל ביותר:דייקסטרה ישלוף מהתור את S ולאחר מכן את A. בשלב זה הוא ייקבע שהמסלול הקל ביותר ל-A הוא S->A, שמשקלו 3. אך למעשה יש מסלול קל יותר, שעובר בקשת שלילית: S->B->A, במשקל 2.

 סיבוכיות זמן ובחירת מבנה נתונים לתור הקדימויות 

בביטויי הסיבוכיות בערך זה, V ו-E מתייחסים למספר הקודקודים והקשתות בגרף (בהתאמה), ולא לקבוצת הקודקודים\קשתות עצמה.

 סיבוכיות זמן 
 ניתוח מקרה גרוע 
כל קודקוד מוכנס ומוצא מתור הקדימיות בדיוק פעם אחת. בגרף מכוון, כל קשת תופיעה פעם אחת בלולאת ה-for (שורה 10), ולכן כמות הקריאות ל-DecreaseKey היא לכל היותר . לכן סיבוכיות הזמן במקרה הגרוע היא:Cormen et al. (2022), עמ' 623-624

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

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

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

תורי הקדימויות המניבים את הסיבוכיות הטובה ביותר מסתמכים על ההבנחה הבאה: במקרה הגרוע, כמות הקריאות ל-DECRESE_KEY גדולה בסדר גודל מכמות הקריאות ל-EXTRACT_MIN (שכן כמות הקשתות בגרף יכולה להגיע לריבוע כמות הקודקודים). כלומר, יש יתרון לתור קדימויות שמאפשר לבצע את DECREASE_KEY בזמן קבוע, ומשאיר את EXTRACT_MIN בזמן לוגריתמי. בעזרת תור קדימויות כזה, אלגוריתם דייקסטרה רץ בזמן.

ישנן מספר ערימות המתאימות לסיבוכיות זו: ערימת פיבונאצ'י (1984), אך נדרש להשתמש בניתוח לשיעורין; Relaxed heap (1988), וריאציה של ערימת פיבונאצ'י שמתאימה לעיבוד מקבילי;  (1996), שאיננו משתמש בניתוח לשיעורין, אך הוא מורכב שלא לצורך, ומניח הנחות לא ריאליסטיות; ו (2012), שנועדה להיות אלטרנטביה פשוטה יותר לתורי ברודאל, ללא ניתוח לשיעורין או הנחות בעייתיות. נחקרו מגוון תורי קדימויות נוספים, שהם מחוץ להיקף הערך.

במודל החישובי הסטנדרטי, לא ניתן לשפר את הסיבוכיות של אלגוריתם דייקסטרה מעבר ל-O(VlogV+E). אחרת, יופר החסם תחתון למיון , שכן דייקסטרה סורק את הקודקודים לפי סדר מרחק עולה.Tarajan et al 2024 pg 2 לכן דייקסטרה לא נופל מכל אלגוריתם מסלולים קלים אחר שמסתמך על מיון קודקודים.
+סיבוכיות מקרה גרועמבנה נתוניםאתחולEXTRACT_MINDECREASE_KEYאלגוריתם דייקסטרההערותרשימה -ערימה בינאריתערימת פיבונאצי, relaxed heapניתוח לשיעורין,. המבוא של מאמר זה מכיל סקירה היסטורית. 

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

נבחן למשל את תור הקדימויות שנבחר בספריות קוד פופולריות: ערימה בינארית נבחרה בספריות בשפת פייתון (NetworkX), C#, ראסט, ו-Go; בעוד ש-Boost, ספריית C++ יעילה ופופולרית, משתמשת בערימה d-ארית (d=4). העדפה זו נתמכת גם על ידי מחקרים אקדמיים שביצעו מבחנים אמפיריים.

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

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

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

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

 מאפשר לדייקסטרה לרוץ בזמן O(E+V*C), שכן הוא מאפשר לבצע DECREASE_KEY ב-O(1) ו-EXTRACT_MIN ב-. תור דלי מנצל את כך שניתן לחלק את המפתחות בתור הקדימויות בין C+1 דליים (כאשר C הוא המשקל המקסימלי בגרף), שכל אחד מכיל רשימה מקושרת של קודקודים בעלי מפתח זהה. ייתכן שהמפתח המזוהה עם דלי ישתנה, אך תמיד יהיה צורך רק ב-C+1 דליים.Melhorn & Sanders (2008), Chapter 10.5: Monotone Integer Priority Queues

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

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

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

עבור גרפים מכוונים, סיבוכיות המקרה הגרוע הטובה ביותר הושגה על ידי Thorup  ב-2004: (O(E+Vloglog(min{V,C}). יש וריאציה של דייקסטרה בעלת זמן ריצה ממוצע ליניארי O(E). עבור גרפים לא מכוונים, ישנה אפילו וריאציה שרצה ב-O(E) במקרה הגרוע.
+סיבוכיות מקרה גרוע (משקלים שלמים)מבנה נתוניםEXTRACT_MINDECREASE_KEYאלגוריתם דייקסטרהתור דלי (שכבה אחת)O(C)O(1)O(E+VC)תור דלי (2 שכבות)O(sqrt(C))O(1)תור דלי עם k שכבותO(k)ערימת בסיס (שכבה אחת)O(logC)O(1)ערימת בסיס (2 שכבות)O(1)הערימה של Thorup (2004)O(1)O(loglogV)O(EloglogV)

 יישומים 

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

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

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

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

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

התמונות הבאות מדגימות את שיפור הביצועים.

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

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

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

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

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

 Transit node routing 
ממוזער|המחשה של transit node routing: המסלולים הקצרים ביותר ממגוון נקודות בעיר מסוימת (לעיר רחוקה אחרת כלשהי) עוברות באותה נקודת יציאה.
מאחר שניווט הוא אחד מהיישומים החשובים של מציאת המסלול הקל ביותר, פותחו אלגוריתמים שמנצלים תכונות של רשתות כבישים. אופטימיזציה נפוצה בתחום זה היא transit node routing . האופטימיזציה מותאמת לכך שידרשו לחשב מספר מסלולים קלים ביותר, ולכן משתלם לבצע עיבוד מקדים.

לרוב, לעיר יש מספר קטן של נקודות יציאה\כניסה. לכן, נסיעות ארוכות לרוב תמיד יעברו באותה קבוצת מצומצמת של קודקודים שמשמשים לכניסה\יציאה מאזורים מיוחדים (למשל ערים). קודקודים אלו נקראים transit nodes. אלגוריתמי transit node routing מחשבים מראש את המסלולים הקצרים ביותר בין ה-transit nodes (ייתכן שבעזרת אלגוריתם דייקסטרה). כשמתקבלת בקשה למציאת מסלול אופטימלי ממקור כלשהו, האלגוריתם מחפש את המסלול שמצמצם את: המרחק מהמקור ל-transit node בעיר של המקור + המרחק מה-transit node של המקור ל-transit node של היעד + המרחק מה-transit node של עיר היעד ליעד עצמו.Melhorn pg. 210

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

ניתן לראות את אלגוריתם דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים.Cormen et al. (2022), עמ' 620Dasgupta et al. (2012), פרק 4.4 בפרט, אלגוריתם דייקסטרה שקול לאלגוריתם חיפוש לרוחב בגרף שבו כל המשקלים שווים ל-1.

סיבוכיות אלגוריתם חיפוש לרוחב היא O(V+E),Cormen et al. (2022), עמ' 558 בהשוואה ל-O(VlogV+E) של דייקסטרה. כלומר, בעיית המסלול הקצר ביותר בגרף לא ממושקל היא קלה יותר מאשר בגרף ממושקל.

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

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

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

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

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

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

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

 המצאת האלגוריתם 
המחקר המתמטי המודרני על מציאת המסלול הקל ביותר בגרף בעל משקלים חיוביים החל בשנות החמישים של המאה ה-20. ב-1956 חוקר ממכון ראנד פרסם תבנית לאלגוריתמים למציאת המסלול הקל ביותר, שאלגוריתם דייקסטרה מיישם. אלגוריתם דייקסטרה פורסם באופן בלתי תלוי ב-1957 על ידי חוקרים ממכון CASE, ב-1959 בידי אדסחר דייקסטרה (שהגה את האלגוריתם כבר ב-1956) וב-1960 על ידי אנשי חקר ביצועים. בנוסף, בתעשייה נעשה שימוש באלגוריתם זהה או דומה, לפחות בפרויקט אחד.לטענות בפסקה זו יש סימוכין בהמשך הפרק, במקומות המתאימים.

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

התבנית של פורד:פורד לא ציין אף כלל לבחירת הקשת . אלגוריתם דייקסטרה בוחר את הקשת  שממזערת את .L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, 1956.

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

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

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

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

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

ב-1957 התפרסם תיאור של האלגוריתם במאמר של חוקרים מ באוהיו. התיאור פורסם בדו"ח שנתי של פרויקט מחקר שבוצע עבור ה-Combat Development Department ב-Electronic Proving Ground של צבא ארצות הברית. המאמר לא התבלט בזמן פרסומו,למשל, בגוגל סקולר ישנם 0 ציטוטים של המאמר מלפני שנת 2000. אך בהסתכלות היסטורית הוא זכור כתגלית עצמאית של אלגוריתם דייקסטרה.

ב-1960 Whiting & Hillier פרסמו מאמר נוסף שתיאר את האלגוריתם. המאמר פורסם בכתב עת העוסק בחקר ביצועים, והמוטיבציה נבעה מבעיות תחבורה ותקשורת.

Dantzig פרסם אלגוריתם דומה ב-1960, אך הוא היה פחות יעיל. 

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

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

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

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


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





 ביאורים 

הערות שוליים

קטגוריה:אופטימיזציה בדידה
דייקסטרה
קטגוריה:הולנד: המצאות