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

↑  מבוסס על Cormen et al. (2022), עמ' 620. פונקציות העזר שוטחו, השמות עובדו לשמות אינדיקטיביים יותר, והקבוצה S נמחקה משום שלא השפיעה על הפונקציונליות.
↑  Dijkstra's Shortest Path Algorithm, brilliant.org (באנגלית אמריקאית)
↑  Mehlhorn & Sanders (2008), עמ' 198
1 2  Cormen et al. (2022), עמ' 620
↑   הרצת האלגוריתם, תוכן מקורס בקמפוס IL, סרטון בערוץ "האוניברסיטה הפתוחה", באתר יוטיוב (אורך: 14:12), 18 אוקטובר 2021
↑  Cormen et al. (2022), עמ' 608
↑  Whyt is the space complexity of Dijkstra with heap O(V) instead of (V + E)?, Stack Overflow (באנגלית)
↑  Dijkstra’s algorithm, TopperWorld (באנגלית)
↑  Cormen et al. (2022), עמ' 611
↑  Cormen et al. (2022), עמ' 605-606
1 2  Greedy Algorithms, brilliant.org (באנגלית אמריקאית)
↑  M. Sniedovich, Dijkstra's algorithm revisited: the dynamic programming connexion, Control and cybernetics 35(3), 2006, עמ' 599-620 (באנגלית)
1 2 3 4  האוניברסיטה הפתוחה, אלגוריתמים, באתר קמפוס IL, קורס אקדמי אינטרנטי
1 2  Jon Kleinberg And Eva Tardos, Chapter 4: Greedy Algorithms, Algorithm Design, Pearson/Addison-Wesley, 2006, ISBN 813170310X, 9788131703106. (באנגלית). ישנה מהדורה מתורגמת: פיתוח אלגוריתמים, בתרגום תמר אלמוג, 2010, הוצאת האוניברסיטה הפתוחה.
1 2  Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Virkumar Vazirani, Algorithms, McGraw-Hill Higher Education, 2006, עמ' 122, ISBN 978-0-07-738849-2. (באנגלית)
1 2 3 4 5  Kurt Mehlhorn, Peter Sanders, Chapter 10: Shortest Paths, Algorithms and Data Structures: The Basic Toolbox, Springer Science & Business Media, 2008, עמ' 198-199, ISBN 978-3-540-77977-3. (באנגלית)
1 2 3 4 5 6 7 8  Cormen et al. (2022), עמ' 623-624
1 2 3 4 5 6 7 8  Alexander Schrijver, On the history of the shortest path problem, Documenta Mathematica Series: Optimization Stories, 2012, עמ' 155-167 doi: 10.4171/DMS/6/19 (באנגלית)
1 2 3 4 5 6  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. המבוא של מאמר זה מכיל סקירה היסטורית.
↑  Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, Network flows: theory, algorithms, and applications, USA: Prentice-Hall, Inc., 1993-02, עמ' 122, ISBN 978-0-13-617549-0. (באנגלית)
1 2  עבור סימוכין לפופולריות, ראה בתת-פרק על ניתוח אמפירי וניתוח מקרה ממוצע.
1 2  Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan, A Back-to-Basics Empirical Study of Priority Queues, Society for Industrial and Applied Mathematics, 2013-12-18, Proceedings, עמ' 61–72
↑  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
1 2  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
1 2 3  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
↑  Gerth Stølting Brodal, Strict Fibonacci Heaps (עמ' 3), מצגת מסימפוזיון, ‏22 במאי 2012 (באנגלית)
↑  Tarajan et al 2024 pg 2
↑  Ulrich Meyer, Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds, Journal of Algorithms, Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms 48, 2003-08-01, עמ' 91–134 doi: 10.1016/S0196-6774(03)00046-4
↑  Tarjan et al. 2024
1 2 3 4  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
↑  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
1 2 3 4 5  A.V. Goldberg, R.E. Tarjan, Expected performance of Dijkstra's shortest path algorithm, 1996
↑  NetworkX source code (v3.4.2) - networkx.algorithms.shortest_paths.weighted
↑  C-Sharp-Algorithms source code - DijkstraShortestPaths.cs, GitHub
↑  petgraph source code - dijkstra.rs, GitHub
↑  graph/paths.go, GitHub
↑  Nimrod Aviram, Y. Shavitt, Optimizing Dijkstra for real-world performance, ArXiv, 2015-05-19
↑  boost source code (v1.87.0) - dijkstra_shortest_paths.hpp
↑  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
↑  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
1 2 3 4 5 6  Melhorn & Sanders (2008), Chapter 10.5: Monotone Integer Priority Queues
↑  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
1 2 3 4 5 6 7 8 9 10  J. Costa, L. Castro, R. de Freitas, Exploring Monotone Priority Queues for Dijkstra Optimization, arXiv, 2024 doi: arXiv:2409.06061
↑  Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, Special Issue on STOC 2003 69, 2004-11-01, עמ' 330–353 doi: 10.1016/j.jcss.2004.04.003
↑  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
1 2 3  Dasgupta et al. (2012), פרק 4.4
↑  Shaull Almagor, Is Dijkstra's algorithm just BFS with a priority queue?, Computer Science Stack Exchange, ‏24 Feb. 2013 (באנגלית)
↑  Cormen et al. (2022), עמ' 558
↑  Cormen, Leiserson, Rivest & Stein, Chapter 22.1, Introduction to Algorithms, 4th edition, The MIT Press, 2022, ISBN 9780262046305. (באנגלית)
↑  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
1 2 3  Dijkstra's single-source shortest path algorithm, אוניברסיטת קורנל, ‏2019 (באנגלית)
↑  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
↑  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
↑  Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993, עמ' 108, ISBN 978-0-13-617549-0. (באנגלית)
↑  לטענות בפסקה זו יש סימוכין בהמשך הפרק, במקומות המתאימים.
↑  L.R. Ford, Jr, Network Flow Theory, Paper P-923, The RAND Corporation, 1956.
1 2 3  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
1 2  E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959-12-01, עמ' 269–271 doi: 10.1007/BF01386390
↑  Numerische Mathematik, The European Digital Mathematics Library
↑  למשל, בגוגל סקולר ישנם 0 ציטוטים של המאמר מלפני שנת 2000.
1 2  P. D. Whiting, J. A. Hillier, A Method for Finding the Shortest Route Through a Road Network, OR 11, 1960, עמ' 37–40 doi: 10.2307/3007178
↑  Paola Festa, Shortest Path Algorithms, Boston, MA: Springer US, 2006, עמ' 185–210, ISBN 978-0-387-30165-5. (באנגלית)
↑  Stuart E. Dreyfus, An Appraisal of Some Shortest-Path Algorithms, Operations Research 17, 1969-06, עמ' 395–412 doi: 10.1287/opre.17.3.395
↑  Tim Greening-Jackson, LEO I and the BR job, Self published, 2012 (באנגלית)
↑   הרצאה של ג'ון גרהאם-קמינגס ב-Strata Conference London 2012, הרצאה בערוץ "O'Reilly", באתר יוטיוב (אורך: 18:24), 2 באוקטובר 2012
דוגמת הרצה של דייקסטרה מהמקור a ליעד b.המספר הכחול מעל לקודקוד מייצג את הערכת המרחק מהמקור (DistEst).
איור להמחשת ההוכחה.

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

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

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