Journal of Formalized Mathematics
Volume 15, 2003
University of Bialystok
Copyright (c) 2003 Association of Mizar Users

## The Underlying Principle of Dijkstra's Shortest Path Algorithm

Jing-Chao Chen
Donghua University, Shanghai
Yatsuka Nakamura
Shinshu University, Nagano

### Summary.

A path from a source vertex $v$ to a target vertex $u$ is said to be a shortest path if its total cost is minimum among all $v$-to-$u$ paths. Dijkstra's algorithm is a classic shortest path algorithm, which is described in many textbooks. To justify its correctness (whose rigorous proof will be given in the next article), it is necessary to clarify its underlying principle. For this purpose, the article justifies the following basic facts, which are the core of Dijkstra's algorithm. \begin{itemize} \itemsep-3pt \item A graph is given, its vertex set is denoted by $V.$ Assume $U$ is the subset of $V,$ and if a path $p$ from $s$ to $t$ is the shortest among the set of paths, each of which passes through only the vertices in $U,$ except the source and sink, and its source and sink is $s$ and in $V,$ respectively, then $p$ is a shortest path from $s$ to $t$ in the graph, and for any subgraph which contains at least $U,$ it is also the shortest. \item Let $p(s,x,U)$ denote the shortest path from $s$ to $x$ in a subgraph whose the vertex set is the union of $\{s,x\}$ and $U,$ and cost $(p)$ denote the cost of path $p(s,x,U),$ cost$(x,y)$ the cost of the edge from $x$ to $y.$ Give $p(s,x,U),$ $q(s,y,U)$ and $r(s,y,U \cup \{x\})$. If ${\rm cost}(p) = {\rm min} \{{\rm cost}(w): w(s,t,U) \wedge t \in V\}$, then we have $${\rm cost}(r) = {\rm min} ({\rm cost}(p)+{\rm cost}(x,y),{\rm cost}(q)).$$ \end{itemize} \noindent This is the well-known triangle comparison of Dijkstra's algorithm.

#### MML Identifier: GRAPH_5

The terminology and notation used in this paper have been introduced in the following articles [13] [16] [14] [17] [4] [3] [6] [15] [1] [8] [9] [2] [10] [5] [12] [7] [11]

#### Contents (PDF format)

1. Preliminaries
2. Additional Properties of Finite Sequences
3. Additional Properties of Chains and Oriented Paths
4. Additional Properties of Acyclic Oriented Paths
5. The Set of the Vertices On a Path or an Edge
6. Directed Paths between Two Vertices
7. Acyclic (or Simple) Paths
8. Weight Graphs and Their Basic Properties
9. Shortest Paths and Their Basic Properties
10. Basic Properties of a Graph with Finite Vertices
11. Three Basic Theorems for Dijkstra's Shortest Path Algorithm

#### Bibliography

[1] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.
[2] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
[3] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
[4] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[5] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.
[6] Czeslaw Bylinski. Finite sequences and tuples of elements of a non-empty sets. Journal of Formalized Mathematics, 2, 1990.
[7] Czeslaw Bylinski. The sum and product of finite sequences of real numbers. Journal of Formalized Mathematics, 2, 1990.
[8] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.
[9] Krzysztof Hryniewiecki. Basic properties of real numbers. Journal of Formalized Mathematics, 1, 1989.
[10] Krzysztof Hryniewiecki. Graphs. Journal of Formalized Mathematics, 2, 1990.
[11] Jaroslaw Kotowicz and Yatsuka Nakamura. Introduction to Go-Board --- part I. Journal of Formalized Mathematics, 4, 1992.
[12] Yatsuka Nakamura and Piotr Rudnicki. Oriented chains. Journal of Formalized Mathematics, 10, 1998.
[13] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.
[14] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.
[15] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.
[16] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.
[17] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.