Revision as of 13:06, 13 November 2023 edit Citation bot (talk \| contribs) Bots 5,873,286 edits Add: s2cid, isbn, pages, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. \| Use this bot. Report bugs. \| Suggested by Headbomb \| Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox \| #UCB_webform_linked 426/763 ← Previous edit		Revision as of 20:05, 30 November 2023 edit undo Citation bot (talk \| contribs) Bots 5,873,286 edits Alter: title, template type. Add: chapter, s2cid. Removed parameters. \| Use this bot. Report bugs. \| Suggested by Headbomb \| Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox \| #UCB_webform_linked 500/1304 Next edit →
Line 81: \| <math>\mathbb{R}</math> \|\| [[Dijkstra's algorithm]] with [[Fibonacci heap]]\|\|<math>O(E+V\log{V})</math> \|\| {{harvnb\|Fredman\|Tarjan\|1984}}, {{harvnb\|Fredman\|Tarjan\|1987}} \|- \| <math>\mathbb{R}</math> \|\| Quantum [[Dijkstra algorithm]] with adjacency list \|\|<math>O(\sqrt{VE}\log^2{V})</math> \|\| Durr et al. 2006<ref>{{Cite journal \|last1=Durr \|first1=Christoph \|last2=Heiligman \|first2=Mark \|last3=Hoyer \|first3=Peter \|last4=Mhalla \|first4=Mehdi \|date=January 2006 \|title=Quantum query complexity of some graph problems \|journal=SIAM Journal on Computing \|volume=35 \|issue=6 \|pages=1310–1328 \|doi=10.1137/050644719 \|arxiv=quant-ph/0401091 \|s2cid=14253494 \|issn=0097-5397}}</ref> \|- \| <math>\mathbb{N}</math> \|\| Dial's algorithm<ref name="dial69">{{cite journal Line 278: {{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 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 ~~journal~~book \|last1=Bernstein \|first1=Aaron \|last2=Nanongkai \|first2=Danupon \|last3=Wulff-Nilsen \|first3=Christian \|~~date=2022 \|title~~chapter=Negative-Weight Single-Source Shortest Paths in Near-linear Time \|~~journal~~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 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}}

Shortest path problem: Difference between revisions