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

Authors
Misra, J
Citation
J. Misra, A walk over the shortest path: Dijkstra's Algorithm viewed as fixed-point computation, INF PROCESS, 77(2-4), 2001, pp. 197-200
Citations number
2
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
77
Issue
2-4
Year of publication
2001
Pages
197 - 200
Database
ISI
SICI code
0020-0190(20010228)77:2-4<197:AWOTSP>2.0.ZU;2-J
Abstract
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, Paralle l Program Design: A Foundation, 1988] is then prescribed whose implementati on results in Dijkstra's algorithm. (C) 2001 Elsevier Science B.V. All righ ts reserved.