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

אלגוריתם דייקסטרה
Dijkstra's algorithm

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

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

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

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

הגדרות

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

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

המסלול הקל ביותר לקודקוד 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

הסבר ואינטואיציה

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

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

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

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

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

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

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

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

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

דוגמת הרצה

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

אינטואיציה

דייקסטרה מגלה את המסלול הקל ביותר תחילה מהקודקודים הקרובים ביותר למקור, ולאחר מכן מקודקודים רחוקים יותר ויותר. למשל, בדוגמת ההרצה הנ"ל תחילה מתגלה המסלול מקודקוד שמרחקו מהמקור הוא 7, לאחר מכן 9, וכו'.

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

תכונות

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

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

ראו גם – אלגוריתם חמדן, תכנון דינמי

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

נכונות

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

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

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

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

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

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

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

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

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

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

בגלל שהקשת uv נשלפה מתור הקדימויות לפני xy, מתקיים $DistEst[u]+w(u\rightarrow v)\leq DistEst[x]+w(x\rightarrow y)$ (במילים: הערכת המשקלים של המסלול P קטנה או שווה להערכת המשקל של המסלול Q). אחרת 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.

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

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

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

בהוכחת הנכונות הנ"ל, הביטוי $DistEst[u]+w(u\rightarrow v)\leq DistEst[x]+w(x\rightarrow y)$ איננו נכון, משום שייתכן ש-w(xy) שלילי. במילים אחרות, דייקסטרה מניח שהמסלול הקל ביותר ל-v חייב לעבור בקודקודים שקרובים יותר למקור. אך כאשר יש צלעות שליליות, לא נכון להניח זאת.

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

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

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

דרוש ידע מוקדם: סיבוכיות זמן, סימון אסימפטוטי

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

סיבוכיות זמן

ניתוח מקרה גרוע

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

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

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

הבחירה הנאיבית ביותר הוא רשימה (זהו גם המימוש שהיה ידוע בשנות החמישים, כשאלגוריתם דייקסטרה הומצא). עלות EXTRACT_MIN היא $O(V)$, ו-DECREASE_KEY ב-$O(1)$ (בהנחה שהקודקודים ממוספרים, או שניתן להגיע אליהם בזמן קבוע באמצעות מצביע). סך הכל זמן הריצה של האלגוריתם הוא $O(V^{2})$. אם הגרף צפוף מאוד ($E=\Theta (V^{2})$), אז זוהי הסיבוכיות הטובה ביותר האפשרית, משום שאי אפשר להתחמק מלסרוק את כל הקשתות בגרף. אך עבור המקרה הכללי, הומצאו מגוון תורי קדימויות יעילים יותר.

בחירה פופולרית הוא ערימה בינארית, שהוצע על ידי וויליאמס ב-1964. בערימה בינארית האתחול לוקח זמן ליניארי, ופעולות ה-EXTRACT_MIN ו-DECREASE_KEY ניתנות לביצוע בזמן לוגריתמי. לכן הסיבוכיות הכוללת של האלגוריתם היא $O(ElogV)$. סיבוכיות זו עדיפה על רשימה כל עוד $E=o(V^{2}/\ logV)$. אופציה נוספת היא ערימה d-ארית, מעין הכללה של ערימה בינארית עם סיבוכיות דומה. על אף שזוהי לא הסיבוכיות מקרה גרוע הטובה ביותר, בפרקטיקה זו בחירה יעילה ופופולרית.

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

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

במודל החישובי הסטנדרטי, לא ניתן לשפר את הסיבוכיות של אלגוריתם דייקסטרה מעבר ל-O(VlogV+E). אחרת, יופר החסם תחתון למיון $\Omega (V\ logV)$, שכן דייקסטרה סורק את הקודקודים לפי סדר מרחק עולה. לכן דייקסטרה לא נופל מכל אלגוריתם מסלולים קלים אחר שמסתמך על מיון קודקודים.

סיבוכיות מקרה גרוע

מבנה נתונים	אתחול	EXTRACT_MIN	DECREASE_KEY	אלגוריתם דייקסטרה	הערות
רשימה	-	$O(V)$	$O(1)$	$O(V^{2})$
ערימה בינארית	$O(V)$	$O(logV)$	$O(logV)$	$O(E\ logV)$
ערימת פיבונאצי, relaxed heap	$O(V)$	$O(logV)$	$O(1)$	$O(V\ logV+E)$	ניתוח לשיעורין
ערימת פיבונאצי חזקה , תור ברודאל

ביצועים פרקטיים וניתוח מקרה ממוצע

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

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

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

גולדברג וטרג'אן (1996) הראו שמספר הקריאות הצפוי ל-DECREASE_KEY חסום על ידי $O(V\ log(1+E/V))$, במודל בו ההנחה היחידה היא שעבור כל קודקוד, משקלי הקשתות מוגרלות באופן בלתי תלוי מאותה התפלגות. זמן הריצה הצפוי של אלגוריתם דייקסטרה עם ערימה בינארית הוא $O(E+V\ logV\ log(1+E/V))$ לעומת $O(E+V\ logV)$ עם ערימת פיבונאצי. לערימת פיבונאצ'י יש יתרון (אסימפטוטי) רק כאשר$E=o(V\ logV\ loglogV)$, ואפילו אז היחס בין זמני הריצה הוא רק $o(loglogV)$, שבפרקטיקה זניח לעומת הגורמים הקבועים בערימת פיבונאצ'י.

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

משקלים שלמים

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

תור דלי מאפשר לדייקסטרה לרוץ בזמן O(E+V*C), שכן הוא מאפשר לבצע DECREASE_KEY ב-O(1) ו-EXTRACT_MIN ב-$O({\sqrt {C}})$. תור דלי מנצל את כך שניתן לחלק את המפתחות בתור הקדימויות בין C+1 דליים (כאשר C הוא המשקל המקסימלי בגרף), שכל אחד מכיל רשימה מקושרת של קודקודים בעלי מפתח זהה. ייתכן שהמפתח המזוהה עם דלי ישתנה, אך תמיד יהיה צורך רק ב-C+1 דליים.

המפתחות בתור תמיד יהיו בטווח בין המינימום הנוכחי $min$ ל-$min+C$, או שהמפתח אינסופי (האלגוריתם טרם סרק את הקודקוד). נוכיח טענה זו כשמורת לולאה : באתחול טענה זו נכונה באופן טריויאלי. בכל איטרציה, בתחילתה מבוצע EXTRACT_MIN שאיננו מקטין את המינימום, ולכן לא מפר את השמורה; ו-DECREASE_KEY גם איננו מפר את השמורה, שכן המפתח החדש הוא: $DistEst[u]+weight(u,v)=min+weight(u,v)\leq min+C$.

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

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

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

סיבוכיות מקרה גרוע (משקלים שלמים)

מבנה נתונים	EXTRACT_MIN	DECREASE_KEY	אלגוריתם דייקסטרה
תור דלי (שכבה אחת)	O(C)	O(1)	O(E+VC)
תור דלי (2 שכבות)	O(sqrt(C))	O(1)	$O(E+V{\sqrt {C}})$
תור דלי עם k שכבות	$O(k+C^{1/k})$	O(k)	$O(kE+V(k+C^{1/k}))$
ערימת בסיס (שכבה אחת)	O(logC)	O(1)	$O(E+V\ logC)$
ערימת בסיס (2 שכבות)	$O(logC/\ loglogC)$	O(1)	$O(E+V\ logC/\ loglogC)$
הערימה של Thorup ‏(2004)	O(1)	O(loglogV)	O(EloglogV)

יישומים

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

מקרים פרטיים

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

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

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

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

פורד (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)$.

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

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

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

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

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

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

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

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

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

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

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

LEO 1 ו-British Railways ‏(1955-1956)

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

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

ראו גם

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

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

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

• אלגוריתם דייקסטרה, באתר MathWorld (באנגלית)
• אלגוריתם דייקסטרה, מחברת קורס מבני נתונים ואלגוריתמים בויקיספר
• מימושים של האלגוריתם בעשרות שפות, באתר Rosetta Code
• יישום המאפשר לראות הרצה של האלגוריתם בצורה אינטרקטיבית וויזואלית, באתר אוניברסיטת סן פרנסיסקו
• "גילוי מחדש" של דייקסטרה באמצעות פיתח מונחה-בדיקות, בבלוג של רוברט מרטין ("הדוד בוב")
• וידאו
  • Dijkstra's algorithm in 3 minutes, סרטון בערוץ "Michael Sambol", באתר יוטיוב (אורך: 2:45)
  • האלגוריתם של דייקסטרה, סרטון בערוץ "ד"ר שרי שינולד", באתר יוטיוב (אורך: 9:49)
  • How Dijkstra's Algorithm Works, סרטון בערוץ "Spanning Tree", באתר יוטיוב (אורך: 8:31)
  • Introduction to Algorithms, Lecture 16: Dijkstra, סרטון בערוץ "MIT", באתר יוטיוב (אורך: 51:25)