A general framework for shortest path algorithms
Wim Pijls, Antoon W. J. Kolen · RePub (Erasmus University Rotterdam) · 1992
In this paper we present a general framework for shortest path algorithms, including amongst others Dijkstra's algorithm and the A* algorithm. By showing that all algorithms are special cases of one algorithm in which some of the nondeterministic choices are made deterministic, termination and correctness can be proved by proving termination and correctness of the root algorithm. Furthermore, several invariants of the algorithms are derived which improve the insight with respect to the operations of the algorithms. 1 Introduction In the context of this paper, the shortest path problem is defined as the problem of finding in a directed graph the shortest path from a source vertex to a set of target vertices. For variations of the problem we refer to the taxonomy of Deo and Pang [Deo-Pang]. The shortest path is a classic topic both in the field of Combinatorial Optimization and in the field of of Artificial Intelligence. In Combinatorial Optimization, the Dijkstra algorithm [Dijkstra] i...