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

DOI10.1016/j.jda.2009.03.001zbMath1186.90119OpenAlexW2095941092WikidataQ59592318 ScholiaQ59592318MaRDI QIDQ972360

James B. Orlin, Kamesh Madduri, K. Subramani and Vahan Mkrtchyan, 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)

Related Items (6)

Dijkstra's algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Running time analysis of ant colony optimization for shortest path problems ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ A new algorithm for the minimum spanning tree verification problem

Uses Software

• Netsoft
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms

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