Dijkstra algorithm

E. W. Dijkstra (1930-2002) proposed in 1959 an algorithm which determines the shortest path between two vertices of a weighted connected graph.

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.

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 outside the subgraph 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 is the minimum between the existing distance and that obtained by adding the weight of the arc to the weight obtained to reach the selected vertex.

This continues until you complete the subgraph completely (or until the selection of the end vertex if it exists). Example:

15e

 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(85A) 217 173 165
F(165B) 217 173 415
E(173A) 217 415 675
C(217A) 403 320 415 675
H(320C) 503 403 415 675487
G(403C) 503 415 487
I(415F) 503 487
J(487H) 503
D(503H)

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.

Optimality
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

 

Publicités