Algorithme de Dijkstra
E. W. Dijkstra (1930-2002) a proposé en 1959 un algorithme (nommé algorithme de Dijkstra) qui permet de déterminer le plus court chemin entre deux sommets d’un graphe 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 programmation dynamique glouton, il visite toutes les solutions possibles.
Conditions
- Pas de longueur négative
- Arc ou arête
- Nombre de sommets fini
- Une source (et accessoirement une cible) définie
L’algorithme de Dijkstra prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source. Il s’agit de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arêtes empruntées.
Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies sauf pour le sommet de départ pour lequel la distance est de 0. Le sous-graphe de départ est l’ensemble vide.
Au cours de chaque itération, on choisit en dehors du sous-graphe un sommet de distance minimale et on l’ajoute au sous-graphe (il devient un sommet visité). Ensuite, on met à jour les distances des sommets voisins de celui ajouté (les sommets sont marqués). La mise à jour s’opère comme suit : la nouvelle distance du sommet voisin est le minimum entre la distance existante et celle obtenue en ajoutant le poids de l’arc entre sommet voisin et sommet ajouté à la distance du sommet ajouté.
On continue ainsi jusqu’à compléter entièrement le sous-graphe (ou jusqu’à sélection du sommet d’arrivée). Exemple :
| distance | à A | à B | à C | à D | à E | à F | à G | à H | à I | à J |
|---|---|---|---|---|---|---|---|---|---|---|
| étape initiale | 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 | ||
| G(403C) | – | – | 503 | – | – | – | – | 415 | 487 | |
| I(415F) | – | – | 503 | – | – | – | – | – | 487 | |
| 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 arbre des chemins les plus courts du sommet A à tous les sommets.
Le sommet de départ est le chemin le plus court pour arriver à lui-même. Ensuite, nous calculons tous les chemins de taille 1 partant de ce sommet, afin d’en valider le plus court. Ce chemin est donc le plus court chemin à partir du sommet de départ car il n’y a pas d’arête de poids négatif. Par récurrence, nous en déduisons que l’algorithme valide toujours un plus court chemin.
d[0]=0, d[i]=infini pour tout sommet autre qu'origine
tant qu'il existe un sommet hors du sous-graphe P
choisir un sommet a hors de P de plus petite distance d[a]
mettre a dans P
pour chaque sommet b hors de P voisin de a
d[b]=min(d[b], d[a]+ poids(a,b))
fin
fin
retourner d
