Shortest path problem: Difference between revisions

Revision as of 11:42, 11 August 2025

Latest revision as of 21:10, 11 August 2025

Line 73:

|-

| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[binary heap]] || <math> O((E+V)\log{V})</math> || {{harvnb|Johnson|1977}}

|-

|- style="background: #d0ffd0"

| <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>|| Dürr et al. 2006<ref>{{Cite journal |last1=Dürr |first1=Christoph |last2=Heiligman |first2=Mark |last3=Høyer |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>

|- style="background: #d0ffd0"

|-

|<math>\mathbb{R}</math>

|[[Dijkstra's algorithm|Dijkstra's]]-[[Bellman–Ford algorithm|Bellman–Ford]] hybrid with a [[Divide-and-conquer algorithm|divide-and-conquer]] frontier reduction

|

|<math>O(E+V \log^{2/3}{V})</math>

|{{harvnb|Duan|Mao|Mao|Shu|Yin|2025}}<ref>{{Cite web |last=Brubaker |first=Ben |date=2025-08-06 |title=New Method Is the Fastest Way To Find the Best Routes |url=https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/ |access-date=2025-08-11 |website=Quanta Magazine |language=en}}</ref>

|-