A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths
In this paper, we propose an efficient method for implementing Dijkstra's algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical...
Main Authors: | Orlin, James B., Madduri, Kamesh, Subramani, K., Williamson, M. |
---|---|
Other Authors: | Sloan School of Management |
Format: | Article |
Language: | en_US |
Published: |
Elsevier
2011
|
Online Access: | http://hdl.handle.net/1721.1/67886 https://orcid.org/0000-0002-7488-094X |
Similar Items
-
Faster algorithms for the shortest path problem
by: Ahuja, Ravindra K.
Published: (2009) -
Faster parametric shortest path and minimum balance algorithms
by: Young, Neal E., et al.
Published: (2009) -
Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs
by: Ramaswamy, Ramkumar, et al.
Published: (2004) -
Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs
by: Ramaswamy, Ramkumar, et al.
Published: (2004) -
Faster All-Pairs Shortest Paths via Circuit Complexity
by: Williams, R Ryan
Published: (2021)