Editing Shortest path problem (section)

==References==

===Notes===
{{reflist|30em}}

===Bibliography===
{{sfn whitelist |CITEREFCormenLeisersonRivestStein2001}}
{{refbegin}}
*{{cite journal |last2=Mehlhorn |first2=Kurt |last3=Orlin |first3=James |last4=Tarjan |first4=Robert E. |date=April 1990 |title=Faster algorithms for the shortest path problem |url=https://apps.dtic.mil/sti/pdfs/ADA194031.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://apps.dtic.mil/sti/pdfs/ADA194031.pdf |archive-date=2022-10-09 |url-status=live |journal=Journal of the ACM |publisher=ACM |volume=37 |issue=2 |pages=213–223 |last1=Ahuja |first1=Ravindra K. |author4-link=Robert Tarjan |doi=10.1145/77600.77615|hdl=1721.1/47994 |s2cid=5499589 |hdl-access=free }}
*{{cite conference
 | last1 = Axiotis | first1 = Kyriakos
 | last2 = Mądry | first2 = Aleksander
 | last3 = Vladu | first3 = Adrian
 | editor-last = Irani | editor-first = Sandy
 | contribution = Circulation control for faster minimum cost flow in unit-capacity graphs
 | doi = 10.1109/FOCS46700.2020.00018
 | pages = 93–104
 | publisher = IEEE
 | title = 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020
 | year = 2020| arxiv = 2003.04863
 }}
* {{cite journal |last=Bellman |first=Richard |year=1958 |title=On a routing problem |journal=Quarterly of Applied Mathematics |volume=16 |pages=87–90 |mr=0102435 |author-link=Richard Bellman |doi=10.1090/qam/102435|doi-access=free }}
*{{Cite conference |last1=Bernstein |first1=Aaron |last2=Nanongkai |first2=Danupon |last3=Wulff-Nilsen |first3=Christian |chapter=Negative-Weight Single-Source Shortest Paths in Near-linear Time |date=2022 |title=2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) |pages=600–611 |publisher=IEEE |doi=10.1109/focs54457.2022.00063|arxiv=2203.03456 |isbn=978-1-6654-5519-0 |s2cid=247958461 }}
*{{cite conference
 | last1 = van den Brand | first1 = Jan
 | last2 = Lee | first2 = Yin Tat
 | last3 = Nanongkai | first3 = Danupon
 | last4 = Peng | first4 = Richard
 | last5 = Saranurak | first5 = Thatchaphol
 | last6 = Sidford | first6 = Aaron
 | last7 = Song | first7 = Zhao
 | last8 = Wang | first8 = Di
 | editor-last = Irani | editor-first = Sandy
 | contribution = Bipartite matching in nearly-linear time on moderately dense graphs
 | doi = 10.1109/FOCS46700.2020.00090
 | pages = 919–930
 | publisher = IEEE
 | title = 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16–19, 2020
 | year = 2020| arxiv = 2009.01802
 }}
*{{cite conference
 | last1 = Chen | first1 = Li
 | last2 = Kyng | first2 = Rasmus
 | last3 = Liu | first3 = Yang P.
 | last4 = Peng | first4 = Richard
 | last5 = Gutenberg | first5 = Maximilian Probst
 | last6 = Sachdeva | first6 = Sushant
 | contribution = Maximum flow and minimum-cost flow in almost-linear time
 | doi = 10.1109/FOCS54457.2022.00064
 | pages = 612–623
 | publisher = IEEE
 | title = 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 – November 3, 2022
 | year = 2022| arxiv = 2203.00671
 }}
*{{cite conference
 | last1 = Cohen | first1 = Michael B.
 | last2 = Mądry | first2 = Aleksander
 | last3 = Sankowski | first3 = Piotr
 | last4 = Vladu | first4 = Adrian
 | editor-last = Klein | editor-first = Philip N.
 | contribution = Negative-weight shortest paths and unit capacity minimum cost flow in <math>\tilde O(m^{10/7}\log W)</math> time
 | doi = 10.1137/1.9781611974782.48
 | pages = 752–771
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proceedings of the Twenty-Eighth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16–19
 | year = 2017}}
*{{Cite conference |last1=Duan|first1=Ran |last2=Mao |first2=Jiayi |last3=Shu |first3=Xinkai |last4=Yin |first4=Longhui |chapter=A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs |date=2023 |title=2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) |pages=484–492 |publisher=IEEE |doi=10.1109/focs57990.2023.00035|arxiv=2307.04139 |isbn=979-8-3503-1894-4 |s2cid=259501045 }}
*{{Cite journal |last2=Goldberg |first2=Andrew V. |last3=Radzik |first3=Tomasz |year=1996 |title=Shortest paths algorithms: theory and experimental evaluation |url=http://ftp.cs.stanford.edu/cs/theory/pub/goldberg/sp-alg.ps.Z |journal=Mathematical Programming |series=Ser. A |volume=73 |issue=2 |pages=129–174 |doi=10.1016/0025-5610(95)00021-6 |mr=1392160 |last1=Cherkassky |first1=Boris V. |author2-link=Andrew V. Goldberg }}
* {{Introduction to Algorithms|edition=2|pages=580–642|chapter=Single-Source Shortest Paths and All-Pairs Shortest Paths}}
*{{cite journal |last=Dantzig |first=G. B. |date=January 1960 |title=On the Shortest Route through a Network |journal=Management Science |volume=6 |issue=2 |pages=187–190 |doi=10.1287/mnsc.6.2.187}}
* {{cite journal |year=1959 |title=A note on two problems in connexion with graphs |journal=Numerische Mathematik |volume=1 |pages=269–271 |doi=10.1007/BF01386390|last1=Dijkstra |first1=E. W. |s2cid=123284777 |author-link=Edsger W. Dijkstra }}
*{{cite conference
 | last = Fineman | first = Jeremy T.
 | editor1-last = Mohar | editor1-first = Bojan
 | editor2-last = Shinkar | editor2-first = Igor
 | editor3-last = O'Donnell | editor3-first = Ryan
 | arxiv = 2311.02520
 | contribution = Single-source shortest paths with negative real weights in <math>\tilde O(mn^{8/9})</math> time
 | doi = 10.1145/3618260.3649614
 | pages = 3–14
 | publisher = Association for Computing Machinery
 | title = Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024
 | year = 2024}}
* {{cite report |last=Ford |first=L. R. |date=1956 |title=Network Flow Theory |place=Santa Monica, CA |publisher=RAND Corporation |id=P-923 |url=http://www.rand.org/pubs/papers/P923.html}}<!--cited in Dijkstra 1959-->
* {{cite conference |last1=Fredman |first1=Michael Lawrence |author-link1=Michael Fredman |first2=Robert E. |last2=Tarjan |author-link2=Robert Tarjan |title=Fibonacci heaps and their uses in improved network optimization algorithms |conference=25th Annual Symposium on Foundations of Computer Science |year=1984 |publisher=[[IEEE]] |pages=338–346 |isbn=0-8186-0591-X |doi=10.1109/SFCS.1984.715934}}
* {{cite journal |last2=Tarjan |first2=Robert E. |year=1987 |title=Fibonacci heaps and their uses in improved network optimization algorithms |journal=Journal of the Association for Computing Machinery |volume=34 |issue=3 |pages=596–615 |doi=10.1145/28869.28874 |last1=Fredman |first1=Michael Lawrence |s2cid=7904683 |author-link1=Michael Fredman |author-link2=Robert Tarjan |doi-access=free }}
* {{cite conference
 | last = Gabow | first = H. N. | author-link = Harold N. Gabow
 | title = Scaling algorithms for network problems
 | doi = 10.1109/SFCS.1983.68
 | pages = 248–258
 | book-title = Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983)
 | year = 1983
 | url = http://www.eecs.umich.edu/%7Epettie/matching/Gabow-scaling-algorithms-for-network-problems.pdf
 }}
*{{cite journal
 | last = Gabow | first = Harold N. | author-link = Harold N. Gabow
 | year = 1985
 | title = Scaling algorithms for network problems
 | journal = [[Journal of Computer and System Sciences]]
 | volume = 31
 | issue = 2
 | pages = 148–168
 | doi = 10.1016/0022-0000(85)90039-X
 | mr = 828519
 | doi-access = free
 }}
*{{cite conference |title=Improved Shortest Paths on the Word RAM |last1=Hagerup |first1=Torben |year=2000 |pages=61–72 |book-title=Proceedings of the 27th International Colloquium on Automata, Languages and Programming |editor1-first=Ugo |editor1-last=Montanari |editor2-first=José D. P. |editor2-last=Rolim |editor3-first=Emo |editor3-last=Welzl |isbn=978-3-540-67715-4 |url=http://dl.acm.org/citation.cfm?id=686343&CFID=563073233&CFTOKEN=28801665}}
* {{cite journal
   | last1 = Henzinger | first1 = Monika R.
   | last2 = Klein | first2 = Philip
   | last3 = Rao | first3 = Satish
   | last4 = Subramanian | first4 = Sairam
   | title = Faster Shortest-Path Algorithms for Planar Graphs
   | journal = Journal of Computer and System Sciences
   | volume = 55
   | issue = 1
   | pages = 3–23
   | year = 1997
   | doi = 10.1006/jcss.1997.1493
   | doi-access = free
  }}
*{{cite journal
 | last = Johnson 
 | first = Donald B.
 | author-link = Donald B. Johnson
 | title = Efficient algorithms for shortest paths in sparse networks
 | journal = [[Journal of the ACM]]
 | volume = 24
 | issue = 1
 | pages = 1–13
 | year = 1977
 | doi=10.1145/321992.321993| s2cid = 207678246
 | doi-access = free
 }}
*{{cite journal
 | last = Johnson | first = Donald B. | date = December 1981
 | title = A priority queue in which initialization and queue operations take {{math|''O''(log log ''D'')}} time
 | journal = Mathematical Systems Theory
 | volume = 15
 | issue = 1
 | pages = 295–309
 | doi = 10.1007/BF01786986
 | mr = 683047
 | s2cid = 35703411 | author-link = Donald B. Johnson
 }}
*{{cite journal
 | last2 = Poblete | first2 = Patricio V.
 | year = 1983
 | title = An {{math|''O''(''m'' log log ''D'')}} algorithm for shortest paths
 | journal = [[Discrete Applied Mathematics]]
 | volume = 6
 | issue = 1
 | pages = 91–93
 | doi = 10.1016/0166-218X(83)90104-X
 | mr = 700028
 | last1 = Karlsson | first1 = Rolf G.
 | doi-access = free
 }}
* {{cite book |title=Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems |last2=Gray |first2=R. S. |last3=Johnson |first3=A. A. |last4=Ladew |first4=W. C. |last5=Meaker |first5=S. R. Jr. |last6=Petry |first6=R. M. |last7=Seitz |first7=R. N. |publisher=Case Institute of Technology |year=1957 |location=Cleveland, Ohio |last1=Leyzorek |first1=M.}}
* {{cite conference |last=Moore |first= E. F. |author-link=Edward F. Moore |year=1959 |title=The shortest path through a maze |pages=285–292 |book-title=Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957) |publisher=Harvard University Press |location=Cambridge }}
*{{cite conference |url=https://archive.org/details/proceedingsofthi2002acms/page/267 |title=Computing shortest paths with comparisons and additions |last2=Ramachandran |first2=Vijaya |year=2002 |isbn=978-0-89871-513-2 |pages=[https://archive.org/details/proceedingsofthi2002acms/page/267 267–276] |last1=Pettie |first1=Seth |book-title=Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms }}
*{{cite journal |last=Pettie |first=Seth |date=26 January 2004 |title=A new approach to all-pairs shortest paths on real-weighted graphs |journal=Theoretical Computer Science |volume=312 |issue=1 |pages=47–74 |doi=10.1016/s0304-3975(03)00402-x|doi-access=free }}
*{{cite journal | last1=Pollack |first1= Maurice |last2=Wiebenson |first2=Walter |date=March–April 1960 |title=Solution of the Shortest-Route Problem—A Review |journal=Oper. Res. |volume=8 |issue=2 |pages=224–230 |doi=10.1287/opre.8.2.224}}  Attributes Dijkstra's algorithm to Minty ("private communication") on p.&nbsp;225.
* {{cite book| title=Combinatorial Optimization — Polyhedra and Efficiency| last=Schrijver| first=Alexander| publisher=Springer| year=2004| isbn=978-3-540-20456-5| series=Algorithms and Combinatorics| volume=24 |at=vol.A, sect.7.5b, p.&nbsp;103}}
* {{cite journal |last=Shimbel |first=Alfonso |year=1953 |title=Structural parameters of communication networks |journal=Bulletin of Mathematical Biophysics |volume=15 |issue=4 |pages=501–507 |doi=10.1007/BF02476438}}
* {{cite conference |last=Shimbel |first=A. |title=Structure in communication nets |location=New York, NY |pages=199–203 |publisher=Polytechnic Press of the Polytechnic Institute of Brooklyn |book-title=Proceedings of the Symposium on Information Networks |year=1955}}
*{{cite journal |date=1999 |title=Undirected single-source shortest paths with positive integer weights in linear time |journal=Journal of the ACM |volume=46 |issue=3 |pages=362–394 |last1=Thorup |first1=Mikkel |doi=10.1145/316542.316548 |s2cid=207654795 |doi-access=free}}
*{{Cite journal |last=Thorup |first=Mikkel |date=2004 |title=Integer priority queues with decrease key in constant time and the single source shortest paths problem |journal=Journal of Computer and System Sciences |volume=69 |issue=3 |pages=330–353 |doi=10.1016/j.jcss.2004.04.003 |doi-access=free}}
*{{cite journal |last2=Hillier |first2=J. A. |date=March–June 1960 |title=A Method for Finding the Shortest Route through a Road Network |journal=Operational Research Quarterly |volume=11 |issue=1/2 |pages=37–40 |last1=Whiting |first1=P. D. |doi=10.1057/jors.1960.32}}
*{{cite conference |last=Williams |first=Ryan |author-link=Ryan Williams (computer scientist) |arxiv=1312.6680 |title=Faster all-pairs shortest paths via circuit complexity |doi=10.1145/2591796.2591811 |mr=3238994 |pages=664–673 |publisher=ACM |location=New York |book-title=Proceedings of the 46th Annual ACM [[Symposium on Theory of Computing]] (STOC '14) |year=2014}}
{{refend}}