A walk over the shortest path: Dijkstra's Algorithm viewed as fixed-point computation

摘要

We present a derivation of Dijkstra's shortest path algorithm [Numer. Math. 1 (1959) 83]. We view the problem as computation of a "greatest solution" of a set of equations. A UNITY-style computation [Chandy and Misra, Parallel Program Design: A Foundation, 1988] is then prescribed whose implementation results in Dijkstra's algorithm.