Semester
Spring
Date of Graduation
2009
Document Type
Thesis
Degree Type
MS
College
Statler College of Engineering and Mineral Resources
Department
Lane Department of Computer Science and Electrical Engineering
Committee Chair
K Subramani
Abstract
This thesis proposes an algorithm that involves Dijkstra's algorithm to solve the Single Source Shortest Path Problem in a graph where the length of each edge is positive, and the specific case where there is a distinct number of possible lengths. Given a graph where there are n vertices, m edges, and K distinct edge lengths, the proposed algorithm runs in O(m ) time if nK ≤ 2m and O(m log nKm ) time if nK > 2m. The algorithm is tested and compared with some of the fastest algorithms for the Single Source Shortest Path Problem for graphs with arbitrary lengths. The results verify the theoretical conclusions that the proposed algorithm is better, in the case where K is small, than the compared algorithms that did not take advantage of having few distinct edge lengths.
Recommended Citation
Williamson, Matthew D., "A faster algorithm for the single source shortest path problem with few distinct positive lengths" (2009). Graduate Theses, Dissertations, and Problem Reports. 4551.
https://researchrepository.wvu.edu/etd/4551