Efficient Shortest Path Algorithms By Graph Decompostion
Diab Abuaiadh, Jeffrey H. Kingston · 2006
This paper introduces a divide-and-conquer approach to the single-source shortest path problem. For an arbitrary digraph with n vertices, m edges, and c cycles, a particular division is exhibited which leads to an O(klogk + m) algorithm, where k = min(n, c), improving on previous methods for near-acyclic digraphs.