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

{{לערוך|שיפורי ניסוח, שימוש עקבי ב-Latex, שיפור ביאורים (האם כולם הכרחיים?).|נושא=מדע וטכנולוגיה|נושא2=מחשוב|כל הערך=כן}}
{{אלגוריתם
| תמונה = קובץ:DijkstraDemo.gif
| כיתוב = אנימציה להמחשת האלגוריתם. משקלי הקשתות שווים למרחק הגאומטרי ביניהן.
| מבנה נתונים = [[תור קדימויות]]
| נקרא על שם = [[אדסחר דייקסטרה]]
| הומצא = 1956
| ממציא = מספר ממציאים בלתי תלויים, ראה [[אלגוריתם דייקסטרה#המצאת האלגוריתם|בהמשך הערך]]
| סיבוכיות מקום = O({{!}}V{{!}})
| סיבוכיות זמן = ישנם מספר מימושים, האופטימלי בהם O({{!}}V{{!}}log{{!}}V{{!}}+{{!}}E{{!}})
| שם בשפת המקור = Dijkstra's algorithm
| שם = אלגוריתם דייקסטרה
}}
'''אלגוריתם דייקסטרה''' הוא [[אלגוריתם]] למציאת המסלול הקל ביותר מקודקוד מקור לקודקוד יעד ב[[גרף ממושקל]] בעל משקלים חיוביים, או למציאת כל המסלולים הקלים ביותר מקודקוד מקור לשאר הקודקודים (בעיית המסלולים הקלים ממקור יחיד). לעיתים מחליפים את המונח "מסלול קל" ב"מסלול קצר" או "מסלול מינימלי".

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

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

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

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

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

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

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

הפסודו קוד מוצא את המסלול הקצר ביותר מהמקור לכל קודקוד בגרף. אם המטרה היא למצוא רק את המסלול הקצר ביותר ממקור ליעד מסוים, ניתן לשנות את תנאי העצירה של הלולאה הראשית כך שיעצור לאחר שקודקוד היעד נשלף מ-Q.<syntaxhighlight lang="text" line="1">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</syntaxhighlight><ref>מבוסס על [[אלגוריתם דייקסטרה#קורמן-2022|Cormen et al. (2022)]], עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.</ref><ref>{{קישור כללי|כתובת=https://brilliant.org/wiki/dijkstras-short-path-finder/|כותרת=Dijkstra's Shortest Path Algorithm|אתר=brilliant.org|שפה=en-us|תאריך_וידוא=2025-01-13}}</ref>

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

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

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

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

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

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

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

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

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

=== דוגמת הרצה ===
[[קובץ:Dijkstra Animation.gif|ללא|מסגרת|דוגמת הרצה של דייקסטרה מהמקור a ליעד b.המספר הכחול מעל לקודקוד מייצג את הערכת המרחק מהמקור (DistEst).]]

=== אינטואיציה ===
דייקסטרה מגלה את המסלול הקל ביותר תחילה מהקודקודים הקרובים ביותר למקור, ולאחר מכן מקודקודים רחוקים יותר ויותר. למשל, בדוגמת ההרצה הנ"ל תחילה מתגלה המסלול מקודקוד שמרחקו מהמקור הוא 7, לאחר מכן 9, וכו'.<ref>[[אלגוריתם דייקסטרה#מלהורן-2008|Mehlhorn & Sanders (2008)]], עמ' 198</ref>

בגרף גאומטרי (משקלים=מרחק גאומטרי), בדומה לדוגמת ההרצה שמופיעה בראש הערך, ניתן לדמיין שמשרטטים עיגול מסביב למקור, ומגדילים הדרגתית את רדיוס העיגול. כשקודקוד נכנס לעיגול, דייקסטרה חישב את המסלול הקל ביותר אליו. ניתן להיעזר באנלוגיה הפיזיקלית הבאה: מתחילים להזרים מים לרשת תעלות (נניח שכל התעלות בעלות קיבולת זהה, ואין הבדלי גבהים). המים יבקרו בקודקודים באותו סדר שדייקסטרה מבקר בהם, וימצאו אותם מסלולים קצרים.<ref name=":9" /><ref>{{יוטיוב|0QIBqnrZup0|3=תוכן מקורס ב[[קמפוס IL]]|שם=הרצת האלגוריתם|ערוץ=[[האוניברסיטה הפתוחה]]|תאריך=18 אוקטובר 2021|אורך=14:12}}</ref> זוהי מעין גרסה "ממושקלת" של [[אלגוריתם חיפוש לרוחב|חיפוש לרוחב]] (ראה פירוט בהמשך הערך).

=== תכונות ===
* האלגוריתם מוצא '''עץ מסלולים מזעריים''' {{אנ|Shortest-path tree}}. זהו [[תת-גרף]] שהוא [[עץ (תורת הגרפים)|עץ]] שמושרש בקודקוד המקור, וכל מסלול מהשורש לכל קודקוד אחר הוא מסלול קל ביותר בגרף המקורי. אם הגרף קשיר, זהו [[עץ פורש]].<ref>[[אלגוריתם דייקסטרה#קורמן-2022|Cormen et al. (2022)]], עמ' 608</ref>
* '''[[סיבוכיות מקום]]''': סיבוכיות המקום היא O(|V|), הנדרשים עבור תור הקדימויות Q והמילון DistEst.<ref>{{קישור כללי|כתובת=https://stackoverflow.com/questions/72457721/whyt-is-the-space-complexity-of-dijkstra-with-heap-ov-instead-of-v-e|כותרת=Whyt is the space complexity of Dijkstra with heap O(V) instead of (V + E)?|אתר=Stack Overflow|שפה=en|תאריך_וידוא=2025-01-04}}</ref><ref>{{קישור כללי|כתובת=https://topperworld.in/media/2024/02/Dijkstra-Algorithm.pdf|כותרת=Dijkstra’s algorithm|אתר=TopperWorld|שפה=en}}</ref>
* אם אין מסלול מהמקור לקודקוד מסוים v, יתקיים DistEst[v]=inf ו-Prev[v]=nil.
* הערכת המרחק תמיד גדולה או שווה למרחק האמיתי.<ref>[[אלגוריתם דייקסטרה#קורמן-2022|Cormen et al. (2022)]], עמ' 611</ref>

=== חמדנות ותכנון דינמי ===
{{ראו גם|ערכים=[[אלגוריתם חמדן]], [[תכנון דינמי]]}}
מאחר שכל מסלול קל ביותר מכיל תת-מסלולים שגם הם מסלולים קלים, לבעיה יש {{קישור שפה|2=Optimal substructure|3=תת-מבנה מיטבי|שם מלא=כן}}. כלומר, הפתרון יכול להבנות מפתרון בעיות קטנות יותר. בעיות מסוג זה מתאימות לפתרון בעזרת [[אלגוריתם חמדן|אלגוריתמים חמדניים]] ו[[תכנון דינמי]].<ref>[[אלגוריתם דייקסטרה#קורמן-2022|Cormen et al. (2022)]], עמ' 605-606</ref><ref name=":24">{{קישור כללי|כתובת=https://brilliant.org/wiki/greedy-algorithm/#applications|כותרת=Greedy Algorithms|אתר=brilliant.org|שפה=en-us|תאריך_וידוא=2025-01-13}}</ref> החמדנות של האלגוריתם באה לידי ביטוי בכך שהאלגוריתם בוחר את הקודקוד שנראה בשלב הנוכחי כקרוב ביותר.<ref name=":24" /> ניתן לראות את הגישה החמדנית כפתרון יעיל של בעיית תכנון דינמי.<ref>{{צ-מאמר|מחבר=M. Sniedovich|שם=Dijkstra's algorithm revisited: the dynamic programming connexion|כתב עת=Control and cybernetics|כרך=35(3)|שנת הוצאה=2006|עמ=599-620|קישור=https://eudml.org/serve/209437/accessibleLayeredPdf/0|שפה=en}}</ref>

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

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

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

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

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

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

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

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

יהי Q מסלול כלשהו מ-s ל-v. נוכיח שמשקלו איננו קטן משל <math>P_v</math>.

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

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

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

ולכן המשקל של המסלול שאלגוריתם דייקסטרה מצא קטן או שווה לכל מסלול אחר מ-s ל-v.<ref name=":5">{{קישור כללי|כתובת=https://campus.gov.il/course/oui-acd-rfp4-algorithm-he/|הכותב=האוניברסיטה הפתוחה|כותרת=אלגוריתמים|אתר=[[קמפוס IL]]|מידע נוסף=קורס אקדמי אינטרנטי}}</ref><ref name=":0">{{צ-ספר|מחבר=Jon Kleinberg And [[אווה טרדוש|Eva Tardos]]|שם=Algorithm Design|מו"ל=Pearson/Addison-Wesley|שנת הוצאה=2006|ISBN=813170310X, 9788131703106|שפה=en|פרק=Chapter 4: Greedy Algorithms|קישור=https://archive.org/details/AlgorithmDesign1stEditionByJonKleinbergAndEvaTardos2005PDF}}. ישנה מהדורה מתורגמת: '''פיתוח אלגוריתמים''', בתרגום תמר אלמוג, 2010, הוצאת האוניברסיטה הפתוחה.</ref>
[[קובץ:DjikstraProof.png|ללא|איור להמחשת ההוכחה.

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

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

אם אלגוריתם דייקסטרה בחר להגיע ל-v עם קשת uv, אז לא ייתכן שניתן למצוא מסלול קל יותר שעובר בקשת xy.{{ביאור|1=האיור מספק אינטואיציה, אך ישנם מקרים שבהם הוא איננו מדויק: ייתכן ש-x=u, y=v או שיש חפיפה בין הקודקודים s,u,x. בנוסף ייתכן שבמסלול מ-y ל-v יש קודקודים נוספים מבין הקודקודים שבוקרו.}}<ref name=":0" />

|מסגרת]]

=== קשתות שליליות ===
כאשר בגרף יש משקלים שליליים, לא מובטח שאלגוריתם דייקסטרה יימצא את המסלול הקצר ביותר.<ref name=":5" />

בהוכחת הנכונות הנ"ל, הביטוי <math>DistEst[u] + w(u \rightarrow v) \leq DistEst[x] + w(x \rightarrow y)</math> איננו נכון, משום שייתכן ש-w(xy) שלילי.<ref name=":5" /> במילים אחרות, דייקסטרה מניח שהמסלול הקל ביותר ל-v חייב לעבור בקודקודים שקרובים יותר למקור. אך כאשר יש צלעות שליליות, לא נכון להניח זאת.<ref name=":26">{{צ-ספר|שם=Algorithms|קישור=http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf|מו"ל=McGraw-Hill Higher Education|שנת הוצאה=2006|ISBN=978-0-07-738849-2|מחבר=Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Virkumar Vazirani|שפה=en|עמ=122}}{{עוגן|DPV}}</ref>

כפי שניתן לראות בדוגמה, יכול להיות מסלול בו קשת חיובית כבדה ש"מחביאה" מדייקסטרה שאחריה יש קשתות שליליות, שיכולות לקזז את הקשת הכבדה, ואף להפוך את המסלול לקל ביותר.
[[קובץ:DijkstraNegativeWeightCounterExample.png|מרכז|ממוזער|דוגמה לגרף בעל משקלות שליליות, שבו דייקסטרה לא יצליח למצוא את המסלול הקל ביותר:דייקסטרה ישלוף מהתור את S ולאחר מכן את A. בשלב זה הוא ייקבע שהמסלול הקל ביותר ל-A הוא S->A, שמשקלו 3. אך למעשה יש מסלול קל יותר, שעובר בקשת שלילית: S->B->A, במשקל 2.<ref name=":26" />]]

== סיבוכיות זמן ובחירת מבנה נתונים לתור הקדימויות{{ביאור|רוב הספרות מתמקדת בהרצה של דייקסטרה על גרף מכוון. אם הגרף לא מכוון, ניתן ליצור גרף חדש שבו כל קשת u-v משוכפלת פעמיים, עבור שני הכיוונים (u->v, v->u). זהו הבדל של קבוע בגודל הקלט, ולכן רוב תוצאות הסיבוכיות עבור גרפים מכוונים תקפים גם לגרפים לא מכוונים. אך תוצאות לגבי אופטימליות, ביצועים פרקטיים וזמן ממוצע לא בהכרח מדויקות.}} ==
{{חומר רקע מקוצר|[[סיבוכיות זמן]], [[סימון אסימפטוטי]]|200px}}
בביטויי הסיבוכיות בערך זה, V ו-E מתייחסים למספר הקודקודים והקשתות בגרף (בהתאמה), ולא לקבוצת הקודקודים\קשתות עצמה.<!-- TODO להוסיף סיכום של הפרק -->

=== סיבוכיות זמן ===
==== ניתוח מקרה גרוע ====
כל קודקוד מוכנס ומוצא מתור הקדימיות בדיוק פעם אחת. בגרף מכוון, כל קשת תופיעה פעם אחת בלולאת ה-for (שורה 10), ולכן כמות הקריאות ל-DecreaseKey היא לכל היותר <math>E</math>. לכן סיבוכיות הזמן במקרה הגרוע היא:<ref name=":14">{{צ-ספר|שם=Algorithms and Data Structures: The Basic Toolbox|קישור=https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ShortestPaths.pdf|מו"ל=Springer Science & Business Media|שנת הוצאה=2008|ISBN=978-3-540-77977-3|מחבר=Kurt Mehlhorn, Peter Sanders|שפה=en|עמ=198-199|פרק=Chapter 10: Shortest Paths}}{{עוגן|מלהורן-2008}}</ref><ref name=":4">[[אלגוריתם דייקסטרה#קורמן-2022|Cormen et al. (2022)]], עמ' 623-624</ref>

<math>O(INITIALIZE+V*EXTRACT\_MIN+E*DECREASE\_KEY)</math>

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

הבחירה הנאיבית ביותר היא [[רשימה (מבנה נתונים)|רשימה]] (זהו גם המימוש שהיה ידוע בשנות החמישים, כשאלגוריתם דייקסטרה הומצא<ref name=":1" /><ref name=":8" />). עלות EXTRACT_MIN היא <math>O(V)</math>, ו-DECREASE_KEY ב-<math>O(1)</math> (בהנחה שהקודקודים ממוספרים, או שניתן להגיע אליהם בזמן קבוע באמצעות [[מצביע]]). סך הכל זמן הריצה של האלגוריתם הוא <math>O(V^2)</math>.<ref name=":4" /> אם הגרף צפוף מאוד (<math>E=\Theta (V^2)</math>), אז זוהי הסיבוכיות הטובה ביותר האפשרית, משום שאי אפשר להתחמק מלסרוק את כל הקשתות בגרף.<ref>{{צ-ספר|שם=Network flows: theory, algorithms, and applications|קישור=https://dl.acm.org/doi/10.5555/137406|מו"ל=Prentice-Hall, Inc.|שנת הוצאה=1993-02|מקום הוצאה=USA|ISBN=978-0-13-617549-0|מחבר=Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin|עמ=122|שפה=en}}</ref> אך עבור המקרה הכללי, הומצאו מגוון תורי קדימויות יעילים יותר.<ref name=":8" />

בחירה פופולרית<ref name=":22">עבור סימוכין לפופולריות, ראה בתת-פרק על ניתוח אמפירי וניתוח מקרה ממוצע.</ref> היא [[ערימה בינארית]], שהוצע על ידי וויליאמס ב-1964.<ref name=":8" /> בערימה בינארית האתחול לוקח זמן ליניארי, ופעולות ה-EXTRACT_MIN ו-DECREASE_KEY ניתנות לביצוע בזמן לוגריתמי. לכן הסיבוכיות הכוללת של האלגוריתם היא <math>O(ElogV)</math>{{ביאור|1=אם הגרף לא [[גרף קשיר|קשיר]], אז הסיבוכיות היא O((V+E)logV). אם הגרף קשיר (כפי שנהוג להניח בטקסטים רבים), אז E=\Omega(V) ולכן ניתן להתייחס לסיבוכיות כ-O(ElogV).|שם=סיבוכיות-ערימה-בינארית}}. סיבוכיות זו עדיפה על רשימה כל עוד <math>E=o(V^2 /\ logV)</math>.<ref name=":4" /> אופציה נוספת היא [[ערימה d-ארית]], מעין הכללה של ערימה בינארית עם סיבוכיות דומה.<ref name=":17">{{צ-ספר|שם=A Back-to-Basics Empirical Study of Priority Queues|קישור=https://epubs.siam.org/doi/abs/10.1137/1.9781611973198.7|מו"ל=Society for Industrial and Applied Mathematics|שנת הוצאה=2013-12-18|עמ=61–72|סדרה=Proceedings|מחבר=Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan}}</ref> על אף שזוהי לא הסיבוכיות מקרה גרוע הטובה ביותר, בפרקטיקה זו בחירה יעילה ופופולרית.<ref name=":22" />

תורי הקדימויות המניבים את הסיבוכיות הטובה ביותר מסתמכים על ההבנחה הבאה: במקרה הגרוע, כמות הקריאות ל-DECRESE_KEY גדולה בסדר גודל מכמות הקריאות ל-EXTRACT_MIN (שכן כמות הקשתות בגרף יכולה להגיע לריבוע כמות הקודקודים). כלומר, יש יתרון לתור קדימויות שמאפשר לבצע את DECREASE_KEY בזמן קבוע, ומשאיר את EXTRACT_MIN בזמן לוגריתמי. בעזרת תור קדימויות כזה, אלגוריתם דייקסטרה רץ בזמן<math>O(VlogV+E)</math>.<ref name=":4" />

ישנן מספר ערימות המתאימות לסיבוכיות זו: [[ערימת פיבונאצ'י]] (1984), אך נדרש להשתמש ב[[ניתוח לשיעורין]];<ref name=":4" /><ref>{{צ-מאמר|מחבר=M.L. Fredman, R.E. Tarjan|שם=Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms|כתב עת=25th Annual Symposium onFoundations of Computer Science, 1984.|שנת הוצאה=1984-10|עמ=338–346|doi=10.1109/SFCS.1984.715934|קישור=https://ieeexplore.ieee.org/document/715934}}</ref> Relaxed heap {{כ}}(1988), וריאציה של ערימת פיבונאצ'י שמתאימה ל[[עיבוד מקבילי]];<ref name=":25">{{צ-מאמר|מחבר=James R. Driscoll, Harold N. Gabow, Ruth Shrairman, Robert E. Tarjan|שם=Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation|כתב עת=Commun. ACM|כרך=31|שנת הוצאה=1988-11-01|עמ=1343–1354|doi=10.1145/50087.50096|קישור=https://dl.acm.org/doi/10.1145/50087.50096}}</ref> {{קישור שפה|2=Brodal queue|3=תור ברודאל}} (1996), שאיננו משתמש בניתוח לשיעורין, אך הוא מורכב שלא לצורך, ומניח הנחות לא ריאליסטיות;<ref name=":8" /><ref name=":18">{{צ-מאמר|מחבר=Michal Mrena, Peter Sedlacek, Miroslav Kvassay|שם=Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths|כתב עת=2019 International Conference on Information and Digital Technologies (IDT)|שנת הוצאה=2019-06|עמ=335–344|doi=10.1109/DT.2019.8813457|קישור=https://ieeexplore.ieee.org/abstract/document/8813457}}</ref> ו{{קישור שפה|2=Strict Fibonacci heap|3=ערימת פיבונאצי חזקה}} (2012), שנועדה להיות אלטרנטביה פשוטה יותר לתורי ברודאל, ללא ניתוח לשיעורין או הנחות בעייתיות.<ref name=":8" /><ref>{{קישור כללי|כתובת=https://cs.au.dk/~gerth/slides/stoc12.pdf|הכותב=Gerth Stølting Brodal|כותרת=Strict Fibonacci Heaps|עמודים=3|מידע נוסף=מצגת מסימפוזיון|תאריך=22 במאי 2012|שפה=en}}</ref> נחקרו מגוון תורי קדימויות נוספים, שהם מחוץ להיקף הערך.

ב[[מודל חישובי|מודל החישובי]] הסטנדרטי{{ביאור|ה-Comparison-addition model, שבו מותר לבצע השוואות וסכימות של המשקלים. ראה התייחסות ל-RAM model בתת-הפרק על משקלים שלמים.}}, לא ניתן לשפר את הסיבוכיות של אלגוריתם דייקסטרה מעבר ל-O(VlogV+E). אחרת, יופר ה[[אלגוריתם מיון#אלגוריתמי מיון מבוססי השוואות|חסם תחתון למיון]] <math>\Omega(V\ logV) </math>, שכן דייקסטרה סורק את הקודקודים לפי סדר מרחק עולה.<ref name=":21">Tarajan et al 2024 pg 2</ref><ref>{{צ-מאמר|מחבר=Ulrich Meyer|שם=Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds|כתב עת=Journal of Algorithms|כרך=48|סדרה=Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms|שנת הוצאה=2003-08-01|עמ=91–134|doi=10.1016/S0196-6774(03)00046-4|קישור=https://www.sciencedirect.com/science/article/abs/pii/S0196677403000464}}</ref>{{ביאור|לא ניתן להתחמק מהופעת E בסיבוכיות משום שהאלגוריתם חייב לסרוק את כל הקשתות בגרף (במקרה הגרוע).}} לכן דייקסטרה לא נופל מכל אלגוריתם מסלולים קלים אחר שמסתמך על מיון קודקודים.<ref name=":15">{{קישור כללי|כתובת=https://arxiv.org/abs/2311.11793|כותרת=Tarjan et al. 2024}}</ref>
{| class="wikitable"
|+סיבוכיות מקרה גרוע
!מבנה נתונים
!אתחול
!EXTRACT_MIN
!DECREASE_KEY
!אלגוריתם דייקסטרה
!הערות
|-
|[[רשימה (מבנה נתונים)|רשימה]]<ref name=":4" /><ref name=":7" />
| -{{ביאור|ניתן להניח שבקלט יש רשימת קודקודים.}}
|<math>O(V)</math>
|<math>O(1)</math>
|<math>O(V^2)</math>
|
|-
|[[ערימה בינארית]]<ref name=":4" />
|<math>O(V)</math>
|<math>O(logV)</math>
|<math>O(logV)</math>
|<math>O(E\ logV)</math>{{ביאור|שם=סיבוכיות-ערימה-בינארית}}
|
|-
|[[ערימת פיבונאצ'י|ערימת פיבונאצי]]<ref name=":4" /><ref name=":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|קישור=https://ieeexplore.ieee.org/document/8813457/}}</ref>, relaxed heap<ref name=":25" />
| rowspan="2" |<math>O(V)</math>
| rowspan="2" |<math>O(logV)</math>
| rowspan="2" |<math>O(1)</math>
| rowspan="2" |<math>O(V\ logV+E)</math>
|[[ניתוח לשיעורין]]
|-
|{{קישור שפה|2=Strict Fibonacci heap|3=ערימת פיבונאצי חזקה}},<ref name=":8">{{צ-מאמר|מחבר=Gerth Stølting Brodal, George Lagogiannis, Robert E. Tarjan|שם=Strict fibonacci heaps|כתב עת=Proceedings of the forty-fourth annual ACM symposium on Theory of computing|סדרה=STOC '12|מו"ל=Association for Computing Machinery|שנת הוצאה=2012-05-19|עמ=1177–1184|doi=10.1145/2213977.2214082|קישור=https://dl.acm.org/doi/abs/10.1145/2213977.2214082}}. המבוא של מאמר זה מכיל סקירה היסטורית.</ref><ref name=":7" /> {{קישור שפה|2=Brodal queue|3=תור ברודאל}}<ref>{{צ-מאמר|מחבר=Gerth Stølting Brodal|שם=Worst-case efficient priority queues|כתב עת=Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms|סדרה=SODA '96|מו"ל=Society for Industrial and Applied Mathematics|שנת הוצאה=1996-01-28|עמ=52–58|doi=10.5555/313852.313883|קישור=https://dl.acm.org/doi/10.5555/313852.313883}}</ref><ref name=":7" />
|
|}

==== ביצועים פרקטיים וניתוח מקרה ממוצע ====
ערימת פיבונאצי (רגילה או חזקה) ותור ברודאל אינם נפוצים בפרקטיקה, משום שהם מורכבים למימוש וברוב המקרים אינם מניבים ביצועים טובים יותר (על אף הסיבוכיות מקרה גרוע הטובה יותר).<ref name=":14" /><ref name=":16" /> הסיבות לפער בין הביצועים האמפיריים לסיבוכיות מקרה גרוע ביותר נובעת מ[[אנליזה של אלגוריתמים#גורמים קבועים|גורמים קבועים]] משמעותיים ש"מוחבאים" בסימון האסימפטוטי, ומפער בין המקרה הגרוע ביותר למקרים נפוצים יותר.<ref name=":14" /><ref name=":18" /><ref name=":16" />

נבחן למשל את תור הקדימויות שנבחר ב[[ספרייה (תכנות)|ספריות קוד]] פופולריות:{{ביאור|ציינתי ספריות רלוונטיות מתוך רשימה של github repository בעלות מעל ל-2,500 כוכבים, ושמתויגות ב-graph-algorithms (ראה רשימה [https://github.com/topics/graph-algorithms כאן]).}} ערימה בינארית נבחרה בספריות בשפת [[פייתון]] ([[NetworkX]]),<ref>{{קישור כללי|כתובת=https://networkx.org/documentation/stable/_modules/networkx/algorithms/shortest_paths/weighted.html#dijkstra_path|כותרת=NetworkX source code (v3.4.2) - networkx.algorithms.shortest_paths.weighted|אתר=|תאריך_וידוא=2025-01-11}}</ref> [[C#]],<ref>{{קישור כללי|כתובת=https://github.com/aalhour/C-Sharp-Algorithms/blob/504140eb7e608bb9dffa8729345f9cd8d476bbcb/Algorithms/Graphs/DijkstraShortestPaths.cs|כותרת=C-Sharp-Algorithms source code - DijkstraShortestPaths.cs|אתר=[[GitHub]]|שפה=|תאריך_וידוא=2025-01-11}}</ref> [[ראסט (שפת תכנות)|ראסט]],<ref>{{קישור כללי|כתובת=https://github.com/petgraph/petgraph/blob/2765d2a55044a35a20d95c50a2f318fbc3bb85f4/src/algo/dijkstra.rs#L2|כותרת=petgraph source code - dijkstra.rs|אתר=[[GitHub]]|תאריך_וידוא=2025-01-11}}</ref> ו-[[Go (שפת תכנות)|Go]]<ref>{{קישור כללי|כתובת=https://github.com/dominikbraun/graph/blob/b8919a8021b1f0342a473db682040f713ba56454/paths.go#L69|כותרת=graph/paths.go|אתר=[[GitHub]]|תאריך_וידוא=2025-01-11}}</ref>; בעוד ש-[[Boost]], ספריית [[C++]] יעילה ופופולרית, משתמשת בערימה d-ארית (d=4).<ref>{{צ-מאמר|מחבר=Nimrod Aviram, Y. Shavitt|שם=Optimizing Dijkstra for real-world performance|כתב עת=ArXiv|שנת הוצאה=2015-05-19|קישור=https://arxiv.org/abs/1505.05033}}</ref><ref>{{קישור כללי|כתובת=https://www.boost.org/doc/libs/1_87_0/boost/graph/dijkstra_shortest_paths.hpp|כותרת=boost source code (v1.87.0) - dijkstra_shortest_paths.hpp|תאריך_וידוא=2025-01-11}}</ref>{{ביאור|האנומליה היא ספריית ה[[ג'אווה (שפת תכנות)|ג'אווה]] JGraphT, שמתממשת ב-{{קישור שפה|3=Pairing heap|2=Pairing heap}} (ראה [https://github.com/jgrapht/jgrapht/blob/49b60d787ca715c0c558f62035dd23eeec57f6b3/jgrapht-core/src/main/java/org/jgrapht/alg/shortestpath/DijkstraShortestPath.java קוד מקור]). ספריית ג'אווה פופולרית נוספת, AlgoDS, מאפשרת לבחור בין מימוש מבוסס רשימה, ערימה בינארית או ערימת פיבונאצי (ראה [https://github.com/sherxon/AlgoDS/blob/master/src/algo/graph/Dijsktra.java קוד מקור]).}} העדפה זו נתמכת גם על ידי מחקרים אקדמיים שביצעו מבחנים אמפיריים.<ref name=":17" /><ref name=":18" /><ref name=":16" /><ref>{{צ-מאמר|מחבר=Rhyd Lewis|שם=A Comparison of Dijkstra's Algorithm Using Fibonacci Heaps, Binary Heaps, and Self-Balancing Binary Trees|כתב עת=Arxiv|שנת הוצאה=2023|doi=10.48550/ARXIV.2303.10034|קישור=https://arxiv.org/abs/2303.10034}}</ref><ref>{{צ-מאמר|מחבר=Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen|שם=The weak-heap family of priority queues in theory and praxis|כתב עת=Proceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 128|סדרה=CATS '12|מו"ל=Australian Computer Society, Inc.|שנת הוצאה=2012-01-31|עמ=103–112|doi=10.5555/2523693.2523707|קישור=https://dl.acm.org/doi/abs/10.5555/2523693.2523707}}</ref>

ניתוח מקרה ממוצע עוזר לתת הסבר תאורטי לפער בין הביצועים בפרקטיקה לסיבוכיות מקרה גרוע. במקרה הגרוע נעשה מספר יוצא דופן של קריאות ל-DECREASE_KEY, ביחס למקרה הממוצע. בממוצע, מספר הקריאות הנוספות ל-DECREASE_KEY (ביחס ל-EXTRACT_MIN) איננו מספיק כדי להצדיק את הגדלת הגורמים הקבועים שנדרשים עבור EXTRACT_MIN (כפי שקורה בערימת פיבונאצ'י).<ref name=":16">{{צ-מאמר|מחבר=A.V. Goldberg, R.E. Tarjan|שם=Expected performance of Dijkstra's shortest path algorithm|שנת הוצאה=1996|קישור=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=83e45698eb1e1df25711bb22910d4e0ea0233efa}}</ref><ref name=":14" />

{{קישור שפה|2=Andrew V. Goldberg|3=אנדרו ו. גולדברג|4=גולדברג}} ו[[רוברט טרג'אן|טרג'אן]] (1996) הראו שמספר הקריאות הצפוי ל-DECREASE_KEY חסום על ידי <math>O(V\ log(1 + E/V))</math>, במודל בו ההנחה היחידה היא שעבור כל קודקוד, משקלי הקשתות [[אי-תלות (הסתברות)|מוגרלות באופן בלתי תלוי]] מאותה [[התפלגות]]. זמן הריצה הצפוי של אלגוריתם דייקסטרה עם ערימה בינארית הוא <math>O(E + V\ log V\ log(1 + E/V)) </math> לעומת <math>O(E+V\ logV) </math> עם ערימת פיבונאצי. לערימת פיבונאצ'י יש יתרון (אסימפטוטי) רק כאשר<math>E=o(V\ logV\ loglogV) </math>, ואפילו אז היחס בין זמני הריצה הוא רק <math>o(loglogV) </math>, שבפרקטיקה זניח לעומת הגורמים הקבועים בערימת פיבונאצ'י.<ref name=":16" />

יש וריאציה של אלגוריתם דייקסטרה בעלת זמן ריצה ממוצע ליניארי (כאשר ידוע חסם למשקל המקסימלי, והמשקלים מתפלגים אחיד).{{ביאור|אם אין תלות בין המשקלים, זמן הריצה מתקיים בסבירות גבוהה.}}<ref name=":6" /><ref>{{צ-מאמר|מחבר=Andrew V. Goldberg|שם=A Practical Shortest Path Algorithm with Linear Expected Time|כתב עת=SIAM Journal on Computing|כרך=37|שנת הוצאה=2008-01|עמ=1637–1655|doi=10.1137/070698774|קישור=https://epubs.siam.org/doi/10.1137/070698774}}</ref>

==== משקלים שלמים ====
אם המשקלים הם מספרים שלמים, יש תורי קדימויות מיוחדים שיכולים לשפר את הסיבוכיות.{{ביאור|אלא אם מצוין אחרת, האלגוריתמים בפרק זה מניחים [[מודל חישובי]] שנקרא {{קישור שפה|2=Random-access machine|3=מכונת RAM}}. בניסוח לא פורמלי, במודל זה הקלט "נכנס" ב[[מילה (מחשב)|מילים]] ב[[זיכרון RAM]] (בניגוד למספרים ממשיים, שבהם עסקנו עד כה). בנוסף ניתן לבצע על המשקלים פעולות אריתמטיות ו[[פעולות על סיביות|פעולות בסיסיות על סיביות]], בדומה למעבד סטנדרטי. ראו למשל [https://ieeexplore.ieee.org/document/10353179 כאן].}}

{{קישור שפה|2=Bucket queue|3=תור דלי}} מאפשר לדייקסטרה לרוץ בזמן O(E+V*C), שכן הוא מאפשר לבצע DECREASE_KEY ב-O(1) ו-EXTRACT_MIN ב-<math>O(\sqrt C)</math>.{{ביאור|מימוש של דייקסטרה באמצעות תור דלי נקרא גם אלגוריתם דייאל (Dial's algorithm), כהוקרה למאמר של רוברט ב. דייאל מ-1969. מבנה הנתונים הוצע באופן בלתי תלוי גם על ידי רוברט ואגנר ב-1976 ו{{קישור שפה|2=Yefim Dinitz|3=יפים דיניץ}} ב-1978.}} תור דלי מנצל את כך שניתן לחלק את המפתחות בתור הקדימויות בין C+1 דליים (כאשר C הוא המשקל המקסימלי בגרף), שכל אחד מכיל רשימה מקושרת של קודקודים בעלי מפתח זהה. ייתכן שהמפתח המזוהה עם דלי ישתנה, אך תמיד יהיה צורך רק ב-C+1 דליים.<ref name=":6">[[אלגוריתם דייקסטרה#מלהורן-2008|Melhorn & Sanders (2008)]], Chapter 10.5: Monotone Integer Priority Queues</ref><ref name=":19">{{צ-מאמר|מחבר=J. Costa, L. Castro, R. de Freitas|שם=Exploring Monotone Priority Queues for Dijkstra Optimization|כתב עת=[[arXiv]]|שנת הוצאה=2024|doi=arXiv:2409.06061|קישור=https://arxiv.org/abs/2409.06061}}</ref>

המפתחות בתור תמיד יהיו בטווח בין המינימום הנוכחי <math>min</math> ל-<math>min+C</math>, או שהמפתח אינסופי (האלגוריתם טרם סרק את הקודקוד). נוכיח טענה זו כ{{קישור שפה|2=Loop invariant|3=שמורת לולאה}}: באתחול טענה זו נכונה באופן טריויאלי. בכל איטרציה, בתחילתה מבוצע EXTRACT_MIN שאיננו מקטין את המינימום, ולכן לא מפר את השמורה; ו-DECREASE_KEY גם איננו מפר את השמורה, שכן המפתח החדש הוא: <math>DistEst[u]+weight(u,v)=min+weight(u,v)\leq min+C</math>.<ref name=":6" /><ref name=":19" />

תור דלי הוא דוגמה בסיסית ל{{קישור שפה|2=Monotone priority queue|3=תורי קדימויות מונוטוניים}}, שהם תורי קדימויות המותאמים למקרים בהם ערך המינימום לא קוטן. הנחה זו מתאימה לדייקסטרה, שסורק קודקודים בסדר עולה של מרחקם מהמקור.<ref name=":6" /><ref name=":19" />

תור קדימויות מונוטוני נוסף הוא {{קישור שפה|2=Radix heap|3=ערימת בסיס}}, שמשפר את תור דלי בכך שדליים מכילים מספר מפתחות, אך דליים של מפתחות שקרובים יותר למינימום יהיו "צרים" יותר (יכילו פחות מפתחות). זמן הריצה של דייקסטרה עם ערימת בסיס הוא <math>O(E+VlogC)</math>, ואם משתמשים בערימת בסיס עם שתי רמות מתקבל זמן ריצה של <math>O(E+VlogC/loglogC)</math>.<ref name=":6" /><ref name=":19" />{{ביאור|ערימות בסיס הוצעו ב-1990 על ידי Ahuja, Mehlhorn, Orlin & Tarjan, על בסיס מחקר של דונלד ג'ונסון מ-1977.}}

עבור גרפים מכוונים, סיבוכיות המקרה הגרוע הטובה ביותר הושגה על ידי Thorup {{אנ|Mikkel Thorup}} ב-2004: (O(E+Vloglog(min{V,C}).<ref>{{צ-מאמר|מחבר=Mikkel Thorup|שם=Integer priority queues with decrease key in constant time and the single source shortest paths problem|כתב עת=Journal of Computer and System Sciences|כרך=69|סדרה=Special Issue on STOC 2003|שנת הוצאה=2004-11-01|עמ=330–353|doi=10.1016/j.jcss.2004.04.003|קישור=https://www.sciencedirect.com/science/article/pii/S002200000400042X?via=ihub}}</ref>{{ביאור|האלגוריתם מניח שניתן לבצע כפל מספרים בזמן קבוע. אחרת, הסיבוכיות מתדרדת ל-O(E+V(loglogmin{V,C})^(1+epsilon)).}}{{ביאור|ישנו גם אלגוריתם בזמן ליניארי O(E), אך הוא מניח [[מודל חישובי]] ייחודי שלא רלוונטי לאף ארכיטקטורת מחשבים מוכרת. ראה [https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20practical%20shortest.pdf כאן בעמוד 1] ו-[https://www.sciencedirect.com/science/article/abs/pii/S0164121204002018 כאן].}} יש וריאציה של דייקסטרה בעלת זמן ריצה ממוצע ליניארי O(E).<ref name=":6" /> עבור גרפים לא מכוונים, ישנה אפילו וריאציה שרצה ב-O(E) במקרה הגרוע.<ref name=":20">{{צ-מאמר|מחבר=Mikkel Thorup|שם=Undirected single-source shortest paths with positive integer weights in linear time|כתב עת=Journal of the ACM|כרך=46|שנת הוצאה=1999-05|עמ=362–394|doi=10.1145/316542.316548|קישור=https://dl.acm.org/doi/10.1145/316542.316548}}</ref>
{| class="wikitable"
|+סיבוכיות מקרה גרוע (משקלים שלמים)
!מבנה נתונים
!EXTRACT_MIN
!DECREASE_KEY
!אלגוריתם דייקסטרה
|-
|תור דלי (שכבה אחת)<ref name=":19" />
|O(C)
|O(1)
|O(E+VC)
|-
|תור דלי (2 שכבות)<ref name=":19" />
|O(sqrt(C))
|O(1)
|<math>O(E+V\sqrt C)</math>
|-
|תור דלי עם k שכבות<ref name=":19" />
|<math>O(k+C^{1/k})</math>
|O(k)
|<math>O(kE+V(k+C^{1/k}))</math>
|-
|ערימת בסיס (שכבה אחת)<ref name=":19" />
|O(logC)
|O(1)
|<math>O(E+V\ logC)</math>
|-
|ערימת בסיס (2 שכבות)<ref name=":19" />
|<math>O(logC/\ loglogC)</math>
|O(1)
|<math>O(E+V\ logC/\ loglogC)</math>
|-
|הערימה של Thorup {{כ}}(2004)<ref name=":19" />
|O(1)
|O(loglogV)
|O(EloglogV)
|}

== יישומים ==
{{להשלים|נושא=מדע וטכנולוגיה|נושא2=מחשוב|פסקה=ראה הערה מוסתרת מתחת לתבנית זו.}}<!-- ראה Network Flows. Theory, Algorithms, and Applications, עמוד 123–124 והפרק שקדם לו. להזכיר את השימוש של דייקסטרה בתקשורת - OSPF ו-IS-IS. -->

== השוואה לאלגוריתמים אחרים ==
=== דייקסטרה כהכללה של אלגוריתם חיפוש לרוחב עבור גרפים ממושקלים ===
{{ראו גם||ערך=[[אלגוריתם חיפוש לרוחב]]}}
ניתן לראות את אלגוריתם דייקסטרה כהכללה של [[אלגוריתם חיפוש לרוחב]] עבור גרפים ממושקלים.<ref name=":9">[[אלגוריתם דייקסטרה#קורמן-2022|Cormen et al. (2022)]], עמ' 620</ref><ref name=":10">[[אלגוריתם דייקסטרה#DPV|Dasgupta et al. (2012)]], פרק 4.4</ref> בפרט, אלגוריתם דייקסטרה שקול לאלגוריתם חיפוש לרוחב בגרף שבו כל המשקלים שווים ל-1.<ref name=":10" /><ref>{{קישור כללי|כתובת=https://cs.stackexchange.com/questions/10047/is-dijkstras-algorithm-just-bfs-with-a-priority-queue/10048#10048|הכותב=Shaull Almagor|כותרת=Is Dijkstra's algorithm just BFS with a priority queue?|אתר=Computer Science Stack Exchange|תאריך=24 Feb. 2013|שפה=en}}</ref>

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

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

=== גרפים בעלי משקלים שליליים ===
{{הפניה לערך מורחב|ערכים=[[אלגוריתם בלמן-פורד]], [[האלגוריתם של ג'ונסון]]}}
האלגוריתם הקלאסי לבעיה זו הוא [[אלגוריתם בלמן-פורד]]. נהוג ללמוד אלגוריתם זה לצד דייקסטרה בקורסי מבוא לאלגוריתמים רבים. בלמן-פורד דומה במובנים מסוימים לדייקסטרה: גם הוא מיישם את התבנית האלגוריתמית של פורד לאלגוריתמים למציאת המסלול הקצר ביותר (ראו בפרק ההיסטוריה),<ref name=":1" /> וגם הוא אלגוריתם חמדן המשתמש בתכנון דינמי.<ref name=":5" />

סיבוכיות הזמן של אלגוריתם בלמן-פורד היא O(VE).<ref name=":23">{{צ-ספר|מחבר=Cormen, Leiserson, Rivest & Stein|שם=Introduction to Algorithms|מו"ל=The MIT Press|שנת הוצאה=2022|ISBN=9780262046305|שפה=en|מהדורה=4th edition|פרק=Chapter 22.1}}{{עוגן|קורמן-2022}}</ref> זו הייתה הסיבוכיות מקרה גרוע הטובה ביותר שהייתה ידועה עד ל-2023, אז פורסם [[אלגוריתם אקראי]] בעל סיבוכיות זמן של Õ(EV^8/9){{ביאור|משמעות הסימון {{קישור שפה|אנגלית|Õ|Õ}} היא O כאשר מתייחסים לגורמים לוגריתמיים כזניחים. כלומר <math>f(n)\in\tilde{O}(g(n))</math> הוא כתיב מקוצר של <math>\exists k:f(n) \in O(g(n) \log^kn)</math> (קורמן ושות', עמ' 73-74)}} בסבירות גבוהה.<ref>{{צ-מאמר|מחבר=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|קישור=https://dl.acm.org/doi/10.1145/3618260.3649614}}</ref> כלומר, בעיית המסלול הקצר ביותר היא קשה יותר כאשר יש בגרף משקלים שליליים.

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

=== שימוש ביוריסטיקות - A* ===
{{הפניה לערך מורחב|אלגוריתם חיפוש A*}}
ניתן לראות את אלגוריתם A* כוראיציה של דייקסטרה שמשתמשת בפונקציית יוריסטיקה כדי למצוא יותר מהר את המסלול הקצר ביותר. ב[[אלגוריתם חיפוש A*|אלגוריתם A*]] נשלף הקודוקד v שממזער את DistEst[v]+h(v), כאשר h היא פונקציית יוריסטיקה האומדת את המרחק מ-v לקודקוד היעד. השוו זאת לדייקסטרה, אשר שולף את הקודקוד שממזער את DistEst[v] בלבד.<ref name=":12">{{קישור כללי|כתובת=https://www.cs.cornell.edu/courses/cs2112/2019fa/lectures/ssp/|כותרת=Dijkstra's single-source shortest path algorithm|אתר=[[אוניברסיטת קורנל]]|תאריך=2019|שפה=en|תאריך_וידוא=2024-12-28}}</ref> דייקסטרה שקול ל-A* אם בוחרים את פונקציית היוריסטיקה h(x)=0.

לעומת דייקסטרה, A* נועד למצוא את המסלול הקצר ביותר בין זוג קודקודים ספציפי, בעוד שדייקסטרה מסוגל לפתור גם את בעיית כל המסלולים הקצרים ממקור יחיד.<ref name=":12" />

במקרים רבים היוריסטיקה מאפשרת לאלגוריתם לנצל ידע חיצוני על הקודקודים. למשל, אם הגרף מייצג מיקומים, ניתן להשתמש במרחק האוקלידי בין v ליעד בתור פונקציית היוריסטיקה. כך אלגוריתם החיפוש יודע לוותר מראש על כיווני חיפוש מיותרים, ו"לכוון" ליעד. עם זאת, כדי להבטיח פלט נכון, ישנם הגבלות מסוימות על פונקציית היוריסטיקה (ראו בערך על האלגוריתם), ועבור קלטים מסוימים פונקציית המרחק האוקלידי לא מקיימת תנאים אלו.<ref name=":12" />
[[קובץ:A Star Algorithm.webm|מסגרת|אנימציות של אלגוריתם A* מחפש את המסלול הקצר ביותר, בשימוש עם יוריסטיקות שונות. באנימציה השמאלית ביותר, אין שימוש ביוריסטיקה, כלומר הריצה שקולה לדייקסטרה. באנימציות מימין לה, מגבירים את המשקל שניתן ליוריסטיקת מרחק אוקלידי. ניתן לראות שזה מאפשר לאלגוריתם לחסוך כיוונים חסרי תועלת, ולהגיע ליעד מהר יותר.|ללא]]

=== מקרים פרטיים ===
עבור גרף לא מכוון, יש [[אלגוריתם אקראי]] שרץ ב-<math>O(E\sqrt{logV\cdot loglogV})</math> ב{{קישור שפה|2=With high probability|3=הסתברות גבוהה}} (כלומר, כשהקלט שואף לאינסוף, ההסתברות שואפת ל-1). האלגוריתם הוא וריאציה על אלגוריתם דייקסטרה, שבה רק תת-קבוצה מצומצמת של הקודקודים נמצאת בתור הקדימויות.<ref name=":11">{{צ-מאמר|מחבר=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|קישור=https://doi.org/10.1109/focs57990.2023.00035}}</ref>

בנוסף, ישנם מקרים פרטיים של גרפים מכוונים בהם ניתן למצוא אלגוריתם בעל סיבוכיות עדיפה מדייקסטרה. ישנם גם שיפורים עבור [[גרף מישורי|גרפים מישוריים]], גרפים חסרי מעגלים, וקלט גאומטרי.<ref>{{צ-מאמר|מחבר=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|קישור=https://epubs.siam.org/doi/10.1137/S0097539702419650}}</ref><ref>{{צ-ספר|שם=Network Flows: Theory, Algorithms, and Applications|קישור=https://books.google.co.il/books/about/Network_Flows.html?id=WnZRAAAAMAAJ&source=kp_book_description&redir_esc=y|מו"ל=Prentice Hall|שנת הוצאה=1993|ISBN=978-0-13-617549-0|מחבר=Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin|שפה=en|עמ=108}}</ref>

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

=== פורד (1956): תבנית לאלגוריתמים למציאת המסלול הקל ביותר ===
{{ראו גם|ערך=[[אלגוריתם בלמן-פורד]] (על שמו של פורד)}}ב-1956 {{קישור שפה|2=L. R. Ford Jr.|3=ל"ר פורד ג'וניור}} מ[[מכון ראנד]] תיאר תבנית לאלגוריתמים למציאת המסלול הקל ביותר. לתבנית זו תואמים אלגוריתם דייקסטרה, כמו גם [[אלגוריתם בלמן-פורד]] המסוגל לעבוד עם משקלים שליליים (וקרוי על שם פורד בזכות תבנית זו). אך התבנית היא כללית, ויכולה להתאים באותה מידה גם לאלגוריתמים בעלי סיבוכיות אקספוננציאלית.

התבנית של פורד:{{מסגרת|נסמן ב-<math>d(v)</math> פונקציה המחזירה את הערכת המרחק מצומת המקור <math>s</math> לכל צומת אחרת <math>v</math> (בדומה ל-DistEst בפסודו-קוד בתחילת הערך).

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

לולאה: באופן איטרטיבי, בחר קשת <math>uv</math> המקיימת <math>d(v)>d(u)+w(uv)</math>, וקבע <math>d(v):=d(u)+w(u,v)</math>.}}פורד לא ציין אף כלל לבחירת הקשת <math>uv</math>. אלגוריתם דייקסטרה בוחר את הקשת <math>uv</math> שממזערת את <math>d(u)</math>.<ref name=":1">{{צ-מאמר|מחבר=Alexander Schrijver|שם=On the history of the shortest path problem|כתב עת=Documenta Mathematica Series:|כרך=Optimization Stories|שנת הוצאה=2012|עמ=155-167|doi=10.4171/DMS/6/19|קישור=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=6eb38c11c7ce6d0711483078a969bf82b83eff9f|שפה=en}}</ref><ref>L.R. Ford, Jr, [https://apps.dtic.mil/sti/tr/pdf/AD0422842.pdf Network Flow Theory], Paper P-923, The RAND Corporation, 1956.</ref>

=== אדסחר דייסקטרה (1956\1959) ===
{{ראו גם|ערך=[[אדסחר דייקסטרה]]}}דייסקטרה תכנן את האלגוריתם ב-1956, במטרה להציג את יכולות המחשב {{קישור שפה|הולנדית|ARMAC (computer)|ARMAC}} בטקס החניכה החגיגי שלו. דייסקטרה רצה לבחור בעיה אלגוריתמית שגם קהל לא מתמטי יוכל להבין. הבעיה שבחר בה הייתה מציאת המסלול הקצר ביותר בין ערים הולנדיות.{{ביאור|הגרף הכיל 64 קודקודים, שכל אחד מהם מייצג עיר בהולנד.}} דייסקטרה מספר שהוא תכנן את האלגוריתם בכ-20 דקות, בזמן הפסקת קפה שלקח כשעשה קניות עם ארוסתו. דייסקטרה האמין שדווקא משום שלא היה יכול להשתמש בעפרון ונייר, הוא אולץ לחשוב על אלגוריתם פשוט ואלגנטי.<ref name=":2">{{צ-מאמר|מחבר=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|קישור=https://dl.acm.org/doi/10.1145/1787234.1787249}}</ref>

דייסקטרה פרסם את האלגוריתם רק כ-3 שנים לאחר המצאתו, ב-1959. תיאור האלגוריתם התפרס על פני עמוד אחד בלבד, מתוך מאמר בן 2.5 עמודים שכלל גם תיאור של אלגוריתם גרפי נוסף.<ref name=":3">{{צ-מאמר|מחבר=E. W. Dijkstra|שם=A note on two problems in connexion with graphs|כתב עת=Numerische Mathematik|כרך=1|שנת הוצאה=1959-12-01|עמ=269–271|doi=10.1007/BF01386390|קישור=https://link.springer.com/article/10.1007/BF01386390}}</ref> המאמר לא עסק בבחירת מימוש לתור הקדימויות (למעשה דייקסטרא כלל לא השתמש במונח זה),<ref name=":3" /> ולכן בטקסטים מודרניים לעיתים מתייחסים לסיבוכיות הזמן של האלגוריתם המקורי כ-<math>O(|V|^2)</math>.<ref name=":14" /><ref name=":1" />

דייסקטרה אמר שב-1956 "אלגוריתם למציאת המסלול הקל ביותר בקושי נחשב למתמטיקה: יש מספר סופי של מסלולים מ-A ל-B וברור שאחד מהם הוא הקצר ביותר, אז על מה כל המהומה?". דייקסטרא החליט לפרסם מאמר על האלגוריתם 3 שנים לאחר המצאתו, כאשר עורך של כתב עת חדש, שעסק גם בנושאים שכיום ייחשבו כחלק ממדעי המחשב,<ref>{{קישור כללי|כתובת=https://eudml.org/journal/10146|כותרת=Numerische Mathematik|אתר=The European Digital Mathematics Library}}</ref> פנה לדייסקטרה ושאל אם יש לו מה לתרום לכתב העת.<ref name=":2" />

בתחילת שנות השישים דייסקטרה נתקל לראשונה בטקסט שקורא לאלגוריתם על שמו, בספר לימוד גרמני.<ref name=":2" />

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

ב-1957 התפרסם תיאור של האלגוריתם במאמר של חוקרים מ{{קישור שפה|2=Case School of Engineering|3=בית הספר קייס להנדה|4=מכון CASE}} ב[[אוהיו]].<ref name=":1" /> התיאור פורסם בדו"ח שנתי של פרויקט מחקר שבוצע עבור ה-Combat Development Department ב-Electronic Proving Ground של [[צבא ארצות הברית]].<ref name=":1" /> המאמר לא התבלט בזמן פרסומו,<ref>למשל, [https://scholar.google.com/scholar?hl=en&as_sdt=2005&sciodt=0%2C5&cites=1778785311229109727&scipsc=&as_ylo=&as_yhi=2000 בגוגל סקולר ישנם 0 ציטוטים של המאמר מלפני שנת 2000].</ref> אך בהסתכלות היסטורית הוא זכור כתגלית עצמאית של אלגוריתם דייקסטרה.<ref name=":1" />

ב-1960 Whiting & Hillier פרסמו מאמר נוסף שתיאר את האלגוריתם.<ref name=":13">{{צ-מאמר|מחבר=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|קישור=https://www.jstor.org/stable/3007178?seq=1#page_scan_tab_contents}}</ref><ref>{{צ-ספר|שם=Shortest Path Algorithms|קישור=https://link.springer.com/chapter/10.1007/978-0-387-30165-5_8|מו"ל=Springer US|שנת הוצאה=2006|מקום הוצאה=Boston, MA|ISBN=978-0-387-30165-5|עמ=185–210|מחבר=Paola Festa|שפה=en}}</ref><ref>{{צ-מאמר|מחבר=Stuart E. Dreyfus|שם=An Appraisal of Some Shortest-Path Algorithms|כתב עת=Operations Research|כרך=17|שנת הוצאה=1969-06|עמ=395–412|doi=10.1287/opre.17.3.395|קישור=https://pubsonline.informs.org/doi/abs/10.1287/opre.17.3.395}}</ref> המאמר פורסם בכתב עת העוסק ב[[חקר ביצועים]], והמוטיבציה נבעה מבעיות תחבורה ותקשורת.<ref name=":13" />

Dantzig פרסם אלגוריתם דומה ב-1960, אך הוא היה פחות יעיל.<ref name=":1" /> <!-- TODO להרחיב בעתיד -->

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

כחלק מפתרון הבעיה, פותח אלגוריתם שאפשר להחשיב כגרסה מוקדמת של אלגוריתם דייסקטרה. עם זאת, האלגוריתם של קולמן כלל הרבה התאמות לבעיה הספציפית של British Railways. בנוסף, האלגוריתם מעולם לא פורסם, והידע שלנו עליו מתבסס על ראיונות שחובבי היסטוריית מחשוב ערכו עם קולמן בשנות האלפיים. קולמן לא המשיך לעסוק במדעי המחשב, ועד לאותם ראיונות הוא לא ידע על קיומו של האלגוריתם של דייסקטרה ועל החשיבות ההיסטורית של המצאתו שלו.<ref>{{צ-מאמר|מחבר=Tim Greening-Jackson|שם=LEO I and the BR job|מו"ל=Self published|שנת הוצאה=2012|קישור=https://www.computinghistory.org.uk/userdata/files/greening-jackson_leobrpaper-1.pdf|שפה=en}}</ref><ref>{{יוטיוב|pcBJfkE5UwU|שם=הרצאה של ג'ון גרהאם-קמינגס ב-Strata Conference London 2012|ערוץ=O'Reilly|תאריך=2 באוקטובר 2012|סוג=הרצאה|אורך=18:24}}</ref>

==ראו גם==
* [[בעיית המסלול הארוך ביותר]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה|Category:Dijkstra's_algorithm}}
* {{MathWorld}}
* [https://he.wikibooks.org/wiki/מבני_נתונים_ואלגוריתמים_-_מחברת_קורס/גרפים/אלגוריתם_Dijkstra אלגוריתם דייקסטרה], מחברת קורס מבני נתונים ואלגוריתמים ב[[ויקיספר|וויקיספר]]
* [https://rosettacode.org/wiki/Dijkstra%27s_algorithm מימושים של האלגוריתם בעשרות שפות], באתר Rosetta Code {{אנ|Rosetta Code}}
* [https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html יישום המאפשר לראות הרצה של האלגוריתם בצורה אינטראקטיבית וויזואלית], באתר [[אוניברסיטת סן פרנסיסקו]]
* [https://blog.cleancoder.com/uncle-bob/2016/10/26/DijkstrasAlg.html "גילוי מחדש" של דייקסטרה באמצעות פיתח מונחה-בדיקות], בבלוג של {{קישור שפה|2=Robert C. Martin|3=רוברט מרטין}} ("הדוד בוב")
* וידאו
** {{יוטיוב|_lHSawdgXpI|שם=Dijkstra's algorithm in 3 minutes|ערוץ=Michael Sambol|אורך=2:45}}
** {{יוטיוב|gAVsc6zmkQg|שם=האלגוריתם של דייקסטרה|ערוץ=ד"ר שרי שינולד|אורך=9:49}}
** {{יוטיוב|EFg3u_E6eHU|שם=How Dijkstra's Algorithm Works|ערוץ=Spanning Tree|אורך=8:31}}
** {{יוטיוב|2E7MmKv0Y24|שם=Introduction to Algorithms, Lecture 16: Dijkstra|ערוץ=[[MIT]]|אורך=51:25}}

== ביאורים ==
{{ביאורים}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

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