Dijkstra's algorithm
EW Dijkstra (1930-2002) proposed in 1959 a algorithm (called Dijkstra's algorithm) which makes it possible to determine the shortest way between two vertices of a graph connected weighted. Dijkstra's algorithm is based on the following observation: once we determine the shortest path to a vertex v, then the paths that go from v to each of its adjacent vertices could be the shortest path to each of these neighboring peaks. Dijkstra's algorithm is an algorithm of dynamic programming gluttonous, he visits all possible solutions.
Conditions
- No negative length
- Arc or edge
- Finite number of vertices
- A source (and incidentally a target) defined
Dijkstra's algorithm takes as input a directed graph weighted by positive reals and a source vertex. This involves progressively building a subgraph in which the different vertices are classified in increasing order of their minimum distance from the starting vertex. The distance corresponds to the sum of the weights of the borrowed edges.
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, we choose outside the subgraph a vertex of minimum distance and we add it to the subgraph (it becomes a visited vertex). Then, we update the distances of the neighboring vertices of the added one (the vertices are marked). The update takes place as follows: the new distance from the neighboring vertex is the minimum between the existing distance and that obtained by adding the weight of the arc between neighboring vertex and vertex added to the distance from the added vertex.
We continue in this way until the subgraph is completely completed (or until the arrival vertex is selected). Example :
| distance | to A | to B | to C | to D | to E | to F | to G | to H | have | to J |
|---|---|---|---|---|---|---|---|---|---|---|
| initial step | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A (0) | 85 | 217 | ∞ | 173 | ∞ | ∞ | ∞ | ∞ | ∞ | |
| B (85TO) | – | 217 | ∞ | 173 | 165 | ∞ | ∞ | ∞ | ∞ | |
| F (165B) | – | 217 | ∞ | 173 | – | ∞ | ∞ | 415 | ∞ | |
| E (173TO) | – | 217 | ∞ | – | – | ∞ | ∞ | 415 | 675 | |
| C (217TO) | – | – | ∞ | – | – | 403 | 320 | 415 | 675 | |
| H (320VS) | – | – | 503 | – | – | 403 | – | 415 | ||
| G (403VS) | – | – | 503 | – | – | – | – | 415 | 487 | |
| I (415F) | – | – | 503 | – | – | – | – | – | 487 | |
| J (487H) | – | – | 503 | – | – | – | – | – | – | |
| D (503H) | – | – | – | – | – | – | – | – | – |
For practical reasons, the resolution of Dijkstra's algorithm only returns a vector containing the visited vertex, the list of predecessors (the already validated vertices) and the values of the shortest paths to all the other vertices. Which corresponds to a current line of the presented table. Using the left column, we can create a tree shortest paths from vertex A to all vertices.
The starting summit 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 summit because there is no edge of negative weight. By induction, we deduce that the algorithm always validates a shorter path.
d [0] = 0, d [i] = infinity for any vertex other than origin
as long as'there is a vertex outside the subgraph P
choose a top To out of P smaller distance d [a]
to put To in P
for each peak b out of P neighbor of To
d [b] = min (d [b], d [a] + weight (a, b))
end
end
return d
EN 
FR 
ES