An improved Dijkstra's shortest path algorithm for sparse network

DOI10.1016/J.AMC.2006.06.094MaRDI QIDQ870157zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 12 March 2007

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2006.06.094

zbMATH Keywords

numerical examplessparse networkscomparison-addition modelDijkstra's shortest path algorithmFibonacci heaproad traffic networks

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• Faster algorithms for the shortest path problem
• scientific article; zbMATH DE number 3937196
• A theorem on the expected complexity of dijkstra's shortest path algorithm
• An improvement of Dijkstra's method for finding a shortest path in a graph
• Speeding up dynamic shortest-path algorithms

Cites work

• scientific article; zbMATH DE number 1576683 (Why is no real title available?)
• scientific article; zbMATH DE number 437547 (Why is no real title available?)
• scientific article; zbMATH DE number 1263219 (Why is no real title available?)
• scientific article; zbMATH DE number 1766771 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• A heuristic algorithm for network equilibration
• A note on two problems in connexion with graphs
• An ‘All Pairs Shortest Paths’ Distributed Algorithm Using 2n2Messages
• Faster Scaling Algorithms for Network Problems
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Improved algorithm for all pairs shortest paths
• On a routing problem

Cited in

(8)

• Dijkstra-based algorithms for the shortest path problem with edges of negative length
• Clifford algebra method for network expression, computation, and algorithm construction
• A theorem on the expected complexity of dijkstra's shortest path algorithm
• Finding the shortest paths by node combination
• Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment
• An improvement of Dijkstra's method for finding a shortest path in a graph
• An improved shortest path algorithm based on Dijkstra for indoor mobile navigation
• Faster algorithms for the shortest path problem

Describes a project that uses

Uses Software

• Algorithm 360

This page was built for publication: An improved Dijkstra's shortest path algorithm for sparse network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870157)