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

DOI10.1016/J.JDA.2009.03.001zbMATH Open1186.90119OpenAlexW2095941092WikidataQ59592318 ScholiaQ59592318MaRDI QIDQ972360FDOQ972360

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

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

zbMATH Keywords

shortest path problemlinear timeDijkstra's algorithmred-blue graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

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

Cited In (14)

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

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)