West Virginia University
A faster algorithm for the single source shortest path problem with few distinct positive lengths
Abstract
dc:description.abstractThis 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.
Degree
thesis:*- Name thesis:degree_name
- MS
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Lane Department of Computer Science and Electrical Engineering
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Williamson, Matthew D.
Subjects
dc:subject × 1Identifiers
dc:identifier.*- Identifier
- https://researchrepository.wvu.edu/etd/4551