A theorem on the expected complexity of dijkstra's shortest path algorithm

DOI10.1016/0196-6774(85)90009-4zbMath0576.68034OpenAlexW2010601538MaRDI QIDQ3696517

Kohei Noshita

Publication date: 1985

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(85)90009-4

zbMATH Keywords

single-source shortest path problemdecision tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (4)

Unnamed Item ⋮ Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment ⋮ The weak-heap data structure: variants and applications ⋮ The expected complexity of Prim's minimum spanning tree algorithm

This page was built for publication: A theorem on the expected complexity of dijkstra's shortest path algorithm