Dijkstra's algorithm

Dijkstra's algorithm

E. W. Dijkstra (1930-2002) a proposé en 1959 un algorithm (nommé algorithme de Dijkstra) qui permet de déterminer le shortest way entre deux sommets d’un graph connexe pondéré. L’algorithme de Dijkstra est basé sur l’observation suivante : une fois que nous déterminons le chemin le plus court vers un sommet v, alors les chemins qui vont de v à chacun de ses sommets adjacents pourraient être le plus court chemin vers chacun de ces sommets voisins. L’algorithme de Dijkstra est un algorithme de dynamic programming glouton, il visite toutes les solutions possibles.

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.

Summit visited: A summit for which we have determined the shortest route. Once we have defined a vertex as VISIT, this is final, and we will not come back to that vertex.
Peak marked : A summit for which a path has been found. We mark this summit as a CANDIDATE for the shortest path.

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 :

shortest path single source dijkstra algorithm
 distanceto Ato Bto Cto Dto Eto Fto Gto Hhaveto J
initial step0
A (0) 85217173
B (85TO) 217173165
F (165B) 217173415
E (173TO) 217415675
C (217TO) 403320415675
H (320VS) 503403415675487
G (403VS) 503415487
I (415F) 503487
J (487H) 503
D (503H) 

Pour des raisons pratiques, la résolution de l’algorithme de Dijkstra ne retourne qu’un vecteur contenant le sommet visité, la liste des prédécesseurs (les sommets déjà validés) et les valeurs des plus courts chemins vers tous les autres sommets. Ce qui correspond à une ligne courante du tableau présenté. Grâce à la colonne de gauche, nous pouvons créer un tree des chemins les plus courts du sommet A à tous les sommets.

shortest path single source dijkstra algorithm
Optimality
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
To share
en_GBEN
%d bloggers like this: