A general framework for shortest path algorithms
January 1992
Research Paper
| Related Files |
|---|
View PDF Version
(eur-few-cs-92-08.pdf, 0.2MB) |
In this paper we present a general framework for shortest path algorithms, including amongst others Dijkstra's algorithm and the A* algorithm. By showing that all algorithms are special cases of one algorithm in which some of the nondeterministic choices are made deterministic, termination and correctness can be proved by proving termination and correctness of the root algorithm. Furthermore, several invariants of the algorithms are derived which improve the insight with respect to the operations of the algorithms.
Keywords
Automatically Extracted Terms
- algorithm
- vertex
- arc algorithm
- version
- iteration
- lemma
- theorem
- s-set algorithm
- proof
- backpointer
- label
- estimate
- cycle
- heuristic
- instance
- vertex v
- s-set
- length
- termination
- f-algorithm
