אלגוריתם דייקסטרה (Hebrew Wikipedia)

Analysis of information sources in references of the Wikipedia article "אלגוריתם דייקסטרה" in Hebrew language version.

refsWebsite

Global rank Hebrew rank

24doi.org

2^nd place

10^th place

8acm.org

1,185^th place

636^th place

5github.com

383^rd place

1,009^th place

4wikipedia.org

low place

4ieee.org

652^nd place

820^th place

4arxiv.org

69^th place

238^th place

4springer.com

274^th place

120^th place

3sciencedirect.com

149^th place

87^th place

3siam.org

low place

4,021^st place

2brilliant.org

low place

2youtube.com

9^th place

2eudml.org

low place

2psu.edu

207^th place

644^th place

1princeton.edu

741^st place

462^nd place

1stackoverflow.com

4,643^rd place

6,213^th place

1topperworld.in

low place

1campus.gov.il

low place

2,227^th place

1archive.org

6^th place

48^th place

1upc.edu

low place

3,446^th place

1mpg.de

1,624^th place

1,679^th place

1au.dk

8,222^nd place

6,504^th place

1networkx.org

low place

1boost.org

low place

1web.archive.org

1^st place

6^th place

1mit.edu

415^th place

289^th place

1cornell.edu

332^nd place

394^th place

1polytechnique.fr

low place

1stackexchange.com

1,983^rd place

699^th place

1google.co.il

2,636^th place

27^th place

1dtic.mil

833^rd place

1,252^nd place

1scholar.google.com

1,697^th place

934^th place

1jstor.org

26^th place

59^th place

1informs.org

low place

3,815^th place

1computinghistory.org.uk

low place

acm.org

dl.acm.org

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. (באנגלית)
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
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
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
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
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
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

archive.org

Jon Kleinberg And Eva Tardos, Chapter 4: Greedy Algorithms, Algorithm Design, Pearson/Addison-Wesley, 2006, ISBN 813170310X, 9788131703106. (באנגלית). ישנה מהדורה מתורגמת: פיתוח אלגוריתמים, בתרגום תמר אלמוג, 2010, הוצאת האוניברסיטה הפתוחה.

arxiv.org

Tarjan et al. 2024
Nimrod Aviram, Y. Shavitt, Optimizing Dijkstra for real-world performance, ArXiv, 2015-05-19
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
J. Costa, L. Castro, R. de Freitas, Exploring Monotone Priority Queues for Dijkstra Optimization, arXiv, 2024 doi: arXiv:2409.06061

au.dk

cs.au.dk

Gerth Stølting Brodal, Strict Fibonacci Heaps (עמ' 3), מצגת מסימפוזיון, ‏22 במאי 2012 (באנגלית)

boost.org

boost source code (v1.87.0) - dijkstra_shortest_paths.hpp

brilliant.org

Dijkstra's Shortest Path Algorithm, brilliant.org (באנגלית אמריקאית)
Greedy Algorithms, brilliant.org (באנגלית אמריקאית)

campus.gov.il

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

computinghistory.org.uk

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

cornell.edu

cs.cornell.edu

Dijkstra's single-source shortest path algorithm, אוניברסיטת קורנל, ‏2019 (באנגלית)

doi.org

dx.doi.org

Alexander Schrijver, On the history of the shortest path problem, Documenta Mathematica Series: Optimization Stories, 2012, עמ' 155-167 doi: 10.4171/DMS/6/19 (באנגלית)
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. המבוא של מאמר זה מכיל סקירה היסטורית.
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
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
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
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
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
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
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
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
Peter Sanders, Dominik Schultes, Engineering Fast Route Planning Algorithms, Experimental Algorithms, Springer, 2007, עמ' 23–36 doi: 10.1007/978-3-540-72845-0_2
Giacomo Nannicini, Daniel Delling, Dominik Schultes, Leo Liberti, Bidirectional A* search on time-dependent road networks, Networks 59, 2012, עמ' 240–251 doi: 10.1002/net.20438
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
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
Philip L. Frana, Thomas J. Misa, An interview with Edsger W. Dijkstra, Communications of the ACM 53, 2010-08, עמ' 41–47 doi: 10.1145/1787234.1787249
E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959-12-01, עמ' 269–271 doi: 10.1007/BF01386390
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
Stuart E. Dreyfus, An Appraisal of Some Shortest-Path Algorithms, Operations Research 17, 1969-06, עמ' 395–412 doi: 10.1287/opre.17.3.395

doi.org

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

dtic.mil

apps.dtic.mil

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

eudml.org

M. Sniedovich, Dijkstra's algorithm revisited: the dynamic programming connexion, Control and cybernetics 35(3), 2006, עמ' 599-620 (באנגלית)
Numerische Mathematik, The European Digital Mathematics Library

github.com

ציינתי ספריות רלוונטיות מתוך רשימה של github repository בעלות מעל ל-2,500 כוכבים, ושמתויגות ב-graph-algorithms (ראה רשימה כאן).
האנומליה היא ספריית הג'אווה JGraphT, שמתממשת ב-Pairing heap (אנ') (ראה קוד מקור). ספריית ג'אווה פופולרית נוספת, AlgoDS, מאפשרת לבחור בין מימוש מבוסס רשימה, ערימה בינארית או ערימת פיבונאצי (ראה קוד מקור).
C-Sharp-Algorithms source code - DijkstraShortestPaths.cs, GitHub
petgraph source code - dijkstra.rs, GitHub
graph/paths.go, GitHub

google.co.il

books.google.co.il

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. (באנגלית)

ieee.org

ieeexplore.ieee.org

אלא אם מצוין אחרת, האלגוריתמים בפרק זה מניחים מודל חישובי שנקרא מכונת RAM (אנ'). בניסוח לא פורמלי, במודל זה הקלט "נכנס" במילים בזיכרון RAM (בניגוד למספרים ממשיים, שבהם עסקנו עד כה). בנוסף ניתן לבצע על המשקלים פעולות אריתמטיות ופעולות בסיסיות על סיביות, בדומה למעבד סטנדרטי. ראו למשל כאן.
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
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
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

informs.org

pubsonline.informs.org

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

jstor.org

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

mit.edu

fab.cba.mit.edu

Robotic Path Planning, Path Planning (באנגלית אמריקאית)

mpg.de

people.mpi-inf.mpg.de

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. (באנגלית)

networkx.org

NetworkX source code (v3.4.2) - networkx.algorithms.shortest_paths.weighted

polytechnique.fr

lix.polytechnique.fr

Giacomo Nannicini, Daniel Delling, Dominik Schultes, Leo Liberti, Bidirectional A* search on time-dependent road networks, Networks 59, 2012, עמ' 240–251 doi: 10.1002/net.20438

princeton.edu

cs.princeton.edu

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

psu.edu

citeseerx.ist.psu.edu

Alexander Schrijver, On the history of the shortest path problem, Documenta Mathematica Series: Optimization Stories, 2012, עמ' 155-167 doi: 10.4171/DMS/6/19 (באנגלית)
A.V. Goldberg, R.E. Tarjan, Expected performance of Dijkstra's shortest path algorithm, 1996

scholar.google.com

למשל, בגוגל סקולר ישנם 0 ציטוטים של המאמר מלפני שנת 2000.

sciencedirect.com

ישנו גם אלגוריתם בזמן ליניארי O(E), אך הוא מניח מודל חישובי ייחודי שלא רלוונטי לאף ארכיטקטורת מחשבים מוכרת. ראה כאן בעמוד 1 ו-כאן.
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
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

siam.org

epubs.siam.org

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
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
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

springer.com

link.springer.com

Peter Sanders, Dominik Schultes, Engineering Fast Route Planning Algorithms, Experimental Algorithms, Springer, 2007, עמ' 23–36 doi: 10.1007/978-3-540-72845-0_2
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck, Route Planning in Transportation Networks, Cham: Springer International Publishing, 2016, עמ' 19–80, ISBN 978-3-319-49487-6. (באנגלית)
E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959-12-01, עמ' 269–271 doi: 10.1007/BF01386390
Paola Festa, Shortest Path Algorithms, Boston, MA: Springer US, 2006, עמ' 185–210, ISBN 978-0-387-30165-5. (באנגלית)

stackexchange.com

cs.stackexchange.com

Shaull Almagor, Is Dijkstra's algorithm just BFS with a priority queue?, Computer Science Stack Exchange, ‏24 Feb. 2013 (באנגלית)

stackoverflow.com

Whyt is the space complexity of Dijkstra with heap O(V) instead of (V + E)?, Stack Overflow (באנגלית)

topperworld.in

Dijkstra’s algorithm, TopperWorld (באנגלית)

upc.edu

algorithmics.lsi.upc.edu

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Virkumar Vazirani, Algorithms, McGraw-Hill Higher Education, 2006, עמ' 122, ISBN 978-0-07-738849-2. (באנגלית)

web.archive.org

Bing Maps New Routing Engine | Maps Blog, web.archive.org, ‏2018-05-26

wikipedia.org

en.wikipedia.org

האנומליה היא ספריית הג'אווה JGraphT, שמתממשת ב-Pairing heap (אנ') (ראה קוד מקור). ספריית ג'אווה פופולרית נוספת, AlgoDS, מאפשרת לבחור בין מימוש מבוסס רשימה, ערימה בינארית או ערימת פיבונאצי (ראה קוד מקור).
אלא אם מצוין אחרת, האלגוריתמים בפרק זה מניחים מודל חישובי שנקרא מכונת RAM (אנ'). בניסוח לא פורמלי, במודל זה הקלט "נכנס" במילים בזיכרון RAM (בניגוד למספרים ממשיים, שבהם עסקנו עד כה). בנוסף ניתן לבצע על המשקלים פעולות אריתמטיות ופעולות בסיסיות על סיביות, בדומה למעבד סטנדרטי. ראו למשל כאן.
מימוש של דייקסטרה באמצעות תור דלי נקרא גם אלגוריתם דייאל (Dial's algorithm), כהוקרה למאמר של רוברט ב. דייאל מ-1969. מבנה הנתונים הוצע באופן בלתי תלוי גם על ידי רוברט ואגנר ב-1976 ויפים דיניץ (אנ') ב-1978.
משמעות הסימון Õ (אנ') היא O כאשר מתייחסים לגורמים לוגריתמיים כזניחים. כלומר $f(n)\in {\tilde {O}}(g(n))$ הוא כתיב מקוצר של $\exists k:f(n)\in O(g(n)\log ^{k}n)$ (קורמן ושות', עמ' 73-74)

youtube.com

הרצת האלגוריתם, תוכן מקורס בקמפוס IL, סרטון בערוץ "האוניברסיטה הפתוחה", באתר יוטיוב (אורך: 14:12), 18 אוקטובר 2021
הרצאה של ג'ון גרהאם-קמינגס ב-Strata Conference London 2012, הרצאה בערוץ "O'Reilly", באתר יוטיוב (אורך: 18:24), 2 באוקטובר 2012