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: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2011
|
| Online Access: | http://hdl.handle.net/1721.1/67886 https://orcid.org/0000-0002-7488-094X |
| _version_ | 1826191771080589312 |
|---|---|
| author | Orlin, James B. Madduri, Kamesh Subramani, K. Williamson, M. |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Orlin, James B. Madduri, Kamesh Subramani, K. Williamson, M. |
| author_sort | Orlin, James B. |
| collection | MIT |
| description | 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 computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in O(m) time if nK=<2m, and O(mlognKm) time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths. |
| first_indexed | 2024-09-23T09:01:01Z |
| format | Article |
| id | mit-1721.1/67886 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:01:01Z |
| publishDate | 2011 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/678862022-09-30T12:49:41Z A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths Orlin, James B. Madduri, Kamesh Subramani, K. Williamson, M. Sloan School of Management Orlin, James B. Orlin, James B. 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 computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in O(m) time if nK=<2m, and O(mlognKm) time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths. United States. Dept. of Energy. Office of Science (contract DE-AC02-05CH11231) United States. Air Force Office of Scientific Research (grant FA9550-06-1-0050) National Science Foundation (U.S.) (award CCF-0827397) 2011-12-28T19:24:59Z 2011-12-28T19:24:59Z 2010-06 Article http://purl.org/eprint/type/JournalArticle 1570-8667 http://hdl.handle.net/1721.1/67886 James B. Orlin, Kamesh Madduri, K. Subramani, and M. Williamson. 2010. A faster algorithm for the single source shortest path problem with few distinct positive lengths. J. of Discrete Algorithms 8, 2 (June 2010), 189-198. DOI=10.1016/j.jda.2009.03.001 http://dx.doi.org/10.1016/j.jda.2009.03.001 https://orcid.org/0000-0002-7488-094X en_US http://dx.doi.org/10.1016/j.jda.2009.03.001 Journal of Discrete Algorithms Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Elsevier Prof. Orlin via Alex Caracuzzo |
| spellingShingle | Orlin, James B. Madduri, Kamesh Subramani, K. Williamson, M. A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths |
| title | A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths |
| title_full | A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths |
| title_fullStr | A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths |
| title_full_unstemmed | A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths |
| title_short | A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths |
| title_sort | faster algorithm for the single source shortest path problem with few distinct positive lengths |
| url | http://hdl.handle.net/1721.1/67886 https://orcid.org/0000-0002-7488-094X |
| work_keys_str_mv | AT orlinjamesb afasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT maddurikamesh afasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT subramanik afasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT williamsonm afasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT orlinjamesb fasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT maddurikamesh fasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT subramanik fasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths AT williamsonm fasteralgorithmforthesinglesourceshortestpathproblemwithfewdistinctpositivelengths |