Modifying Dijkstra's Algorithm to Solve Many Instances of SSSP in Linear Time

Otte, Michael Wilson

Reports

Modifying Dijkstra's Algorithm to Solve Many Instances of SSSP in Linear Time Public Deposited

Analytics

Citations

Citeable URL: https://scholar.colorado.edu/concern/reports/sx61dn18v

Abstract

We show that for graphs with positive edge weights the single-source shortest path planning problem (SSSP) can be solved using a novel partial ordering over nodes, instead of a full ordering, without sacrificing algorithmic correctness. The partial ordering we investigate is defined with respect to carefully chosen (but easy to calculate) "approximate" level-sets of shortest-path length. We present a family of easy-to-implement "approximate'' priority heaps, based on an array of linked-lists, that create this partial ordering automatically when used directly by Dijkstra's SSSP algorithm. For graphs G = (E,V) with positive edge lengths, and depending on which version of the heap is used, the resulting Dijkstra variant runs in either time O(|E| + |V | + K) with space O(|E| + |V | + l_max/l_min) or time O((|E| + |V|) log_w(l_max/l_min + 1)) with space O(|E| + log_w(l_max/l_min + 1)), where l_min and l_max are the minimum (non-zero) and maximum (finite) edge lengths, respectively, and w is the word length of the computer being used (e.g., 32 or 64 in most cases), and K is a function of G such that K = O(|E|) for many common types of graphs (e.g., K = 1 for graphs with unit edge lengths). We also describe a linear time pre-/post-processing procedure that extends these results to undirected graphs with non-negative edge weights. Thus, it possible to solve many instances of SSSP in O(|E| + |V |); for these instances our method ties the fastest known runtime for SSSP, while having smaller constant factor overhead than previous methods. This work can be viewed as an extension of Dial’s SSSP algorithm in order handle floating point edge weights, faster runtimes, and new theoretical results.

Creator