TY - JOUR

T1 - Calculating path algorithms

AU - Backhouse, R.C.

AU - van den Eijnde, J.P.H.W.

AU - Gasteren, van, A.J.M.

PY - 1994

Y1 - 1994

N2 - A calculational derivation is given of two abstract path algorithms. The first is an all-pairs algorithm, two well-known instances of which are Warshall's (reachability) algorithm and Floyd's shortest-path algorithm; instances of the second are Dijkstra's shortest-path algorithm and breadth-first/depth-first search of a directed graph. The basis for the derivations is the algebra of regular languages.

AB - A calculational derivation is given of two abstract path algorithms. The first is an all-pairs algorithm, two well-known instances of which are Warshall's (reachability) algorithm and Floyd's shortest-path algorithm; instances of the second are Dijkstra's shortest-path algorithm and breadth-first/depth-first search of a directed graph. The basis for the derivations is the algebra of regular languages.

U2 - 10.1016/0167-6423(94)90005-1

DO - 10.1016/0167-6423(94)90005-1

M3 - Article

VL - 22

SP - 3

EP - 19

JO - Science of Computer Programming

JF - Science of Computer Programming

SN - 0167-6423

IS - 1-2

ER -