Principes de l’algorithme de Dijkstra

Publié en 1959, l’algorithme de Dijkstra est une alternative à celui de Floyd, alternative plus complexe, mais également beaucoup plus rapide. En fait, le résultat fourni par Dijkstra n’est pas tout à fait le même que celui fourni par Floyd : on se fixe un sommet source, et Dijkstra donne tous les chemins les plus courts de ce sommet source à chacun des autres sommets et ce en O(aln n) . Ainsi, pour le même résultat, Floyd tourne en O(n3) tandis que Dijkstra tourne en O(a2ln n) où a est le nombre d’arêtes du graphe (supposé connexe, rappelons-le), donc O(n).

Description de l’algorithme

L’algorithme de Dijkstra est un algorithme de type glouton : à chaque nouvelle étape, on traite un nouveau sommet. Reste à définir le choix du sommet à traiter, et le traitement à lui infliger, bref l’algorithme…

Tout au long du calcul, on va donc maintenir deux ensembles :

  • C, l’ensemble des sommets qui restent à visiter ; au départ C=S-{source}
  • D, l’ensemble des sommets pour lesquels on connaît déjà leur plus petite distance à la source ; au départ, D={source}.

L’algorithme se termine bien évidemment lorsque C est vide.

Pour chaque sommet s dans D, on conservera dans un tableau distances le poids du plus court chemin jusqu'à la source, et dans un tableau parcours le sommet p qui le précède dans un plus court chemin de la source à s. Ainsi, pour retrouver un chemin le plus court, il suffira de remonter de prédécesseur en prédécesseur jusqu'à la source, ce qui pourra se faire grâce à un unique appel récursif (beaucoup moins coûteux que dans le cas de Floyd…).

Initialisation

Au début de l’algorithme, le chemin le plus court connu entre la source et chacun des sommets est le chemin direct, avec une arête de poids infini s'il n’y a pas de liaison entre les deux sommets. On initialise donc le tableau distances par les poids des arêtes reliant la source à chacun des sommets, et le tableau parcours par source pour tous les sommets.

ième étape

On suppose avoir déjà traité i sommets, parcours et distances contiennent respectivement les poids et le prédécesseur des plus courts chemins pour chacun des sommets déjà traités.

Soit s le sommet de C réalisant le minimum de distances[s]. On supprime s de C et on l’ajoute à D. Reste à mettre à jour les tableaux distances et parcours pour les sommets t reliés directement à s par une arête comme suit : si distances[s] + F(s,t) < distances[t], alors on remplace distances[t] par distances[s] + F(s,t) et parcours[t] par s… et c'est tout !

(n-2)ème étape

Au départ, il y a (n-1) sommets à visiter, mais comme on le verra ci-après, la dernière étape est inutile puisqu'elle n’apporte rien. Ainsi, dès la (n-2)ème étape, distances et parcours contiennent toute l’information nécessaire pour trouver des plus courts chemins de la source à chacun des autres sommets (car alors D=S):

  • distances[s] est le poids du plus court chemin de la source à s
  • parcours[t] est le prédécesseur de s dans un plus court chemin de la source à s

Preuve de l’algorithme

Il reste à prouver que cet algorithme fonctionne bel et bien, ce qui à première vue n’est pas franchement une évidence. La récurrence à effectuer repose sur les deux hypothèses suivantes :

  • Les tableaux distances et parcours permettent d’obtenir pour tous les points s de D un plus court chemin qui mène de la source à s
  • Les tableaux distances et parcours permettent d’obtenir pour tous les points t de C un plus court chemin qui mène de la source à t en ne passant que par des points de D.

Ces deux hypothèses sont bien vérifiées à l’initialisation des tableaux, si elles le sont encore à l’arrivée, comme D=S , la deuxième hypothèse fournit la preuve de l’algorithme.

Supposons donc ces hypothèses vérifiées à une étape donnée de l’algorithme. Soit s le sommet de C qui minimise le tableau distances. Montrons que les deux hypothèses sont encore valables pour DU{s} et C-{s} .

Scheme du passage de s de C dans D

Soit p=parcours[s] . D’après la première hypothèse, il existe un plus court chemin c allant de la source à p et ne passant que par des points de D. Montrons que cU(p,s) (en trait plein et épais sur le dessin précédent) est un chemin minimal de la source à s. Par l’absurde, si ce n’était pas le cas, on pourrait trouver un autre chemin plus court qui entre nécessairement dans l’ensemble C par un certain sommet t (sinon on contredit la deuxième hypothèse) différent de s (en pointillés épais sur le dessin). Or, d’après le choix de s, distances[s] < distances[t] , donc comme toutes les arêtes sont de poids positifs, ce nouveau chemin passant par t aura un poids supérieur ou égal au poids de cU(p,s) . Ainsi, cU(p,s) est bien un chemin minimal de la source à s, la première hypothèse sera bien vérifiée au début de l’étape suivante.

Pour démontrer la seconde hypothèse appliquée à DU{s} , considérons un sommet u de C distinct de s. De deux choses l’une : soit on peut trouver un plus court chemin de la source à u en ne passant que par des points de DU{s}, , soit il n’y a rien à modifier et c'est fini. Si on peut effectivement trouver un plus court chemin, il passe par s d’après la deuxième hypothèse appliquée à D. Il reste à voir que cU(p,s)U(s,u) (en pointillés fins sur le dessin) est bien un plus court chemin de la source à u en ne passant que par des sommets de DU{s} . Considérons donc un tel chemin, passant par s. S'il retourne dans D, il faut nécessairement qu'il ressorte de D en un certain sommet v. Mais v a été incorporé à D avant s, donc il existe un chemin de la source à v plus court que cU(p,s) , et a fortiori plus court que cU(p,s)U(s,u) , ce qui voudrait dire que notre chemin ne passe pas par s. Ainsi, ce chemin ne retourne pas dans D et est donc bien de la forme escomptée. La mise à jour des tableaux parcours et distances réalise les modifications nécessaires pour les seuls sommets où il peut y avoir lieu de modifier quelque chose, c'est-à-dire ceux directement reliés à s.

Ouf ! L’algorithme fonctionne bien, tant mieux ! On remarque aussi que la dernière étape (la (n-1)ème) ) est inutile, puisque, comme il ne reste qu'un seul sommet t dans C, un plus court chemin ne passant que par des sommets de D=S-{t} est un plus court chemin de la source à t.

Evaluation

Schématiquement, on pourrait représenter l’algorithme de Dijkstra de la manière suivante :

   

Pour i=1 à n-2 Faire
   s = Extraire_Minimum(C)
   Pour tous les sommets (de C) reliés à s // (Pour toutes les arêtes partant de s) 
        Si (il le faut) Mettre_a_jour(distances,parcours)
Suivant i

La boucle intérieure devrait être uniquement effectuée sur des sommets de C. En pratique, la distinction entre les extrémités des arêtes appartenant à C et les autres ne peut se faire sans test. Comme de toute façon le test (il le faut) renvoie "faux" pour les sommets de D (sommets déjà traités), on peut étendre la boucle à tous les sommets du graphe reliés à s sans perte de temps. La mise à jour des tableaux se fait en temps constant tout comme le test (il le faut), l’extraction du minimum en O(ln n) . La boucle intérieure est exécutée en tout et pour tout a fois où a est le nombre d’arêtes du graphe. Le graphe est connexe, donc n=O(a) . Bref, un algorithme en O(a nln n) , c'est merveilleux… mais ce n’est pas le résultat annoncé !

Cherchons l’erreur… Elle tient "simplement" au fait que la fonction d’extraction du minimum attend aussi en argument la relation d’ordre qui existe sur ce tas, i.e. s=Extraire_Minimum(C,inf) . Mais cette fonction inf dépend de la distance minimale du sommet considéré à la source, distance variant d’étape en étape en fonction du tableau distances ! L’algorithme ainsi écrit est donc faux…

Il faut ainsi, après chaque modification de la relation d’ordre, s'assurer que le tas reste tas, ce qui peut se faire à l’aide d’une simple percolation. En effet, considérons un sommet t pour lequel il est nécessaire de modifier les tableaux distances et parcours. t ne peut que se "rapprocher" de la source, donc il ne peut que remonter dans le tas. Concrètement, on obtient l’algorithme suivant :


Pour i=1 à n Faire
   s=Extraire_Minimun(C,inf)
   Pour tous les sommets t reliés à s // ( = Pour toutes les arêtes partant de s) 
      Si (il le faut) 
        Mettre_a_jour(distances,parcours)
        Percolation(t) 
      Fin Si
Suivant i

Reprenons le calcul précédent : sans la boucle intérieure, l’algorithme tourne en O(nln n) . La boucle intérieure est exécutée a fois. On a donc au maximum a percolations, chacune en O(ln n) . Par conséquent, l’algorithme final tourne en O((n+a)ln n) , ou, puisque n=O(a) , en O(aln n).