Calculating path algorithms
- Backhouse, Roland C.
- van den Eijnde, J.P.H.W.
- van Gasteren, A.J.M.
DOIAbstract
AbstractA 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
Add to ORKG