Calculating path algorithms

R.C. Backhouse; J.P.H.W. van den Eijnde; A.J.M. Gasteren, van

doi:10.1016/0167-6423(94)90005-1

Calculating path algorithms

R.C. Backhouse
, J.P.H.W. van den Eijnde
, A.J.M. Gasteren, van

Research output: Contribution to journal › Article › Academic › peer-review

18 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	3-19
Journal	Science of Computer Programming
Volume	22
Issue number	1-2
DOIs	https://doi.org/10.1016/0167-6423(94)90005-1
Publication status	Published - 1994

Access to Document

10.1016/0167-6423(94)90005-1

Cite this

@article{ddd093d3c9934524b886b68159f0b3e1,

title = "Calculating path algorithms",

abstract = "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.",

author = "R.C. Backhouse and \{van den Eijnde\}, J.P.H.W. and \{Gasteren, van\}, A.J.M.",

year = "1994",

doi = "10.1016/0167-6423(94)90005-1",

language = "English",

volume = "22",

pages = "3--19",

journal = "Science of Computer Programming",

issn = "0167-6423",

publisher = "Elsevier B.V.",

number = "1-2",

}

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

SN - 0167-6423

VL - 22

SP - 3

EP - 19

JO - Science of Computer Programming

JF - Science of Computer Programming

IS - 1-2

ER -

Calculating path algorithms

Abstract

Access to Document

Fingerprint

Cite this