A faster algorithm for the single source shortest path problem with few distinct positive lengths
Matthew D. Williamson · 2009
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.