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. 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.

Visited vertex: A vertex for which we have determined the shortest path to it.
Once we set a vertex as VISITED, that is final, and we won’t visit that vertex again.
Marked vertex: A vertex for which a path to it has been found. We mark that
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:

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. Thanks to the left column, we can create a tree of shortest paths from vertex A to any vertices.

dijkstra

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