A faster algorithm for the single source shortest path problem with few distinct positive lengths

DOI10.1016/J.JDA.2009.03.001MaRDI QIDQ972360zbMATH OpenOpenAlexWikidataFDO

Authors James B. Orlin, Kamesh Madduri, K. Subramani, Matthew Williamson

Publication date 25 May 2010

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

Full work available at URL https://doi.org/10.1016/j.jda.2009.03.001

zbMATH Keywords

shortest path problemlinear timeDijkstra's algorithmred-blue graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Undirected single-source shortest paths with positive integer weights in linear time
• A novel single source shortest path algorithm
• A new algorithm for the shortest-path problem
• scientific article; zbMATH DE number 1926665
• scientific article; zbMATH DE number 613343

Cites work

• scientific article; zbMATH DE number 1875419 (Why is no real title available?)
• A note on two problems in connexion with graphs
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Introduction to algorithms
• Network flows. Theory, algorithms, and applications.
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

Cited in

(14)

• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Locality-based relaxation: an efficient method for GPU-based computation of shortest paths
• Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment
• Running time analysis of ant colony optimization for shortest path problems
• Using petal-decompositions to build a low stretch spanning tree
• An algorithmic framework for the single source shortest path problem with applications to disk graphs
• A simple ant colony optimizer for stochastic shortest path problems
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• A new algorithm for the minimum spanning tree verification problem
• Computing single source shortest paths using single-objective fitness
• scientific article; zbMATH DE number 7121921 (Why is no real title available?)
• A novel single source shortest path algorithm
• Simpler computation of single-source shortest paths in linear average time

Describes a project that uses

Uses Software

• Netsoft
• DIMACS

This page was built for publication: A faster algorithm for the single source shortest path problem with few distinct positive lengths

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