Calculating path algorithms

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

Research output: Contribution to journalArticleAcademicpeer-review

14 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 languageEnglish
Pages (from-to)3-19
JournalScience of Computer Programming
Volume22
Issue number1-2
DOIs
Publication statusPublished - 1994

Fingerprint

Formal languages
Directed graphs
Algebra

Cite this

Backhouse, R. C., van den Eijnde, J. P. H. W., & Gasteren, van, A. J. M. (1994). Calculating path algorithms. Science of Computer Programming, 22(1-2), 3-19. https://doi.org/10.1016/0167-6423(94)90005-1
Backhouse, R.C. ; van den Eijnde, J.P.H.W. ; Gasteren, van, A.J.M. / Calculating path algorithms. In: Science of Computer Programming. 1994 ; Vol. 22, No. 1-2. pp. 3-19.
@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",
number = "1-2",

}

Backhouse, RC, van den Eijnde, JPHW & Gasteren, van, AJM 1994, 'Calculating path algorithms', Science of Computer Programming, vol. 22, no. 1-2, pp. 3-19. https://doi.org/10.1016/0167-6423(94)90005-1

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

In: Science of Computer Programming, Vol. 22, No. 1-2, 1994, p. 3-19.

Research output: Contribution to journalArticleAcademicpeer-review

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 -

Backhouse RC, van den Eijnde JPHW, Gasteren, van AJM. Calculating path algorithms. Science of Computer Programming. 1994;22(1-2):3-19. https://doi.org/10.1016/0167-6423(94)90005-1