E. W. Dijkstra (1930-2002) proposed in 1959 an algorithm which determines the shortest path between two vertices of a weighted connected graph. The algorithm is based on the following observation: once we determine the shortest path to a vertex v, then the paths that continue from v to each of its adjacent vertices could be the shortest path to each of those neighbour vertices. Dijkstra’s algorithm is a greedy dynamic programming algorithm, it visits all possible solutions.
Conditions
- No negative weight
- Directed or undirected
- Finite number of vertices
- A defined source
The algorithm takes as input an oriented graph weighted by positive real numbers and a source vertex. It is a question of gradually building a subgraph in which the different vertices are classified in ascending order of their minimum distance to the starting vertex. The distance is the sum of the weights of the borrowed edges.
Once we set a vertex as VISITED, that is final, and we won’t visit that vertex again.
path as a CANDIDATE for the shortest path to that vertex.
Initially, we consider that the distances from each vertex to the starting vertex are infinite except for the starting vertex for which the distance is 0. The starting subgraph is the empty set.
During each iteration, a vertex of minimum distance is selected (it becomes a visited vertex) outside the subgraph (from marked vertices) and added to the subgraph. Then, we update the distances of the vertices next to the one added. The update takes place as follows: the new distance from the neighboring vertex (becomes a marked vertex) is the minimum between the existing distance and that obtained by adding the weight of the arc to the weight obtained to reach the visited vertex.
This continues until you complete the subgraph completely (or until the selection of the end vertex if it exists). Example:
distance | to A | to B | to C | to D | to E | to F | to G | to H | to I | to J |
---|---|---|---|---|---|---|---|---|---|---|
init | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
A(0) | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ | |
B(85_{A}) | – | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ | |
F(165_{B}) | – | 217 | ∞ | 173 | – | ∞ | ∞ | 415 | ∞ | |
E(173_{A}) | – | 217 | ∞ | – | – | ∞ | ∞ | 415 | 675 | |
C(217_{A}) | – | – | ∞ | – | – | 403 | 320 | 415 | 675 | |
H(320_{C}) | – | – | 503 | – | – | 403 | – | 415 | ||
G(403_{C}) | – | – | 503 | – | – | – | – | 415 | 487 | |
I(415_{F}) | – | – | 503 | – | – | – | – | – | 487 | |
J(487_{H}) | – | – | 503 | – | – | – | – | – | – | |
D(503_{H}) | – | – | – | – | – | – | – | – | – |
For practical reasons, the resolution of the Dijkstra algorithm only returns a vector containing the visited vertex, the list of predecessors (the vertices already validated) and the values of the shortest paths to all the other vertices. Which corresponds to a current line of the table. Thanks to the left column, we can create a tree of shortest paths from vertex A to any vertices.
The start vertex is the shortest way to reach itself. Then, we compute all the size 1 paths starting from this vertex, in order to validate the shortest one. This path is therefore the shortest path from the starting vertex because there is no edge of negative weight. By recurrence, we deduce that the algorithm always validates a shorter path.
d[0]=0, d[i]=infini While'it exists an unvisited vertix from the subgraph P choose a vertex a outside P which has the shortest distance d[a] put a in P For each vertex b outside P which is in the neigborhood of a d[b]=min(d[b], d[a]+ poids(a,b)) end end return d