Dijkstra Shortest Path
Dijkstra’s Shortest Path Algorithm. We implement and prove correct Dijkstra’s algorithm for the single source shortest path problem, conceived in 1956 by E. Dijkstra. The algorithm is implemented using the data refinement framework for monadic, nondeterministic programs. An efficient implementation is derived using data structures from the Isabelle Collection Framework.
Keywords for this software
References in zbMATH (referenced in 9 articles )
Showing results 1 to 9 of 9.
- Lammich, Peter: Refinement to imperative HOL (2019)
- Lammich, Peter; Lochbihler, Andreas: Automatic refinement to efficient data structures: a comparison of two approaches (2019)
- Lammich, Peter; Sefidgar, S. Reza: Formalizing network flow algorithms: a refinement approach in Isabelle/HOL (2019)
- Zhan, Bohua: Efficient verification of imperative programs using auto2 (2018)
- Lammich, Peter; Sefidgar, S. Reza: Formalizing the Edmonds-Karp algorithm (2016)
- Lammich, Peter: Refinement to Imperative/HOL (2015)
- Noschinski, Lars: A graph library for Isabelle (2015)
- Alkassar, Eyad; Böhme, Sascha; Mehlhorn, Kurt; Rizkallah, Christine: A framework for the verification of certifying computations (2014)
- Omodeo, Eugenio G.; Tomescu, Alexandru I.: Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets (2014)