A Linear Iterative Approach for Hierarchical Shortest Path Finding

Abstract

We present a hierarchical approach that subdivides a network with $n$ vertices into $r$ regions with the same number $m$ of vertices ($n = r m$) and creates higher levels merging a constant number $c$ of adjacent regions. We propose linear iterative algorithms to find a shortest path and to expand this path into the lowest level. Since our approach is non-recursive, the complexity constants are small and the algorithms are more efficient in practice than other recursive optimal approaches. A hybrid shortest path algorithm to perform intra-regional queries in the lowest level is introduced. This strategy uses a subsequence of vertices that belong to the shortest path while actually computing the whole shortest path. The hybrid algorithm requires $O(m)$ time and space assuming an uniform distribution of vertices. This represents a further improvement concerning space, since a path view approach requires $O(m^{1.5})$ space in the lowest level. For higher $k$-levels, a path view approach spends $O(1)$ time and requires $O(c^k m)$ space. (UMIACS-TR-2002-97)