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.

, ,
Erasmus School of Economics

Pijls, W., & Kolen, A. W. J. (1992). A general framework for shortest path algorithms. Retrieved from