Qu'est-ce que Algorithme de Dijkstra ?
Algorithme qui trouve les plus courts chemins d'un sommet de départ vers tous les sommets d'un graphe dont les poids des arêtes sont supérieurs ou égaux à 0. Il fixe de façon répétée le sommet le plus proche dont la distance n'est pas encore définitive et met à jour les distances de ses voisins. Il ne fonctionne pas correctement avec des poids d'arêtes négatifs.
Nom japonais: ダイクストラ法
« Algorithme de Dijkstra » apparaît dans 3 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.
Domaine: Structures de données et algorithmes
Procédure
On fixe la distance du départ à 0 et celle de tous les autres sommets à l'infini, et on marque tous les sommets comme non définitifs. On prend le sommet non définitif de plus petite distance, on le rend définitif et, pour chaque arête qui en part, on met à jour la distance du sommet à l'autre extrémité si « distance définitive + poids de l'arête » est inférieur à sa distance actuelle (relâchement). On répète jusqu'à ce que tous les sommets soient définitifs. En enregistrant le sommet précédent à chaque mise à jour, on peut ensuite retracer le plus court chemin lui-même.
Poids négatifs et autres algorithmes
L'algorithme de Dijkstra rend les sommets définitifs en supposant que passer par d'autres sommets ne peut qu'allonger une distance, jamais la raccourcir. Avec des arêtes négatives, une distance définitive peut ensuite devenir plus courte, si bien que des réponses correctes ne sont pas garanties. En présence de poids négatifs, on utilise l'algorithme de Bellman-Ford, qui relâche toutes les arêtes V−1 fois et peut aussi détecter les cycles négatifs. Pour les plus courts chemins entre toutes les paires de sommets, on utilise aussi l'algorithme de Floyd-Warshall (O(V³)), fondé sur la programmation dynamique. Dans le routage réseau, les protocoles à état de liens comme OSPF utilisent l'algorithme de Dijkstra dans chaque routeur pour calculer les routes.
Questions fréquentes
Quel est le lien entre l'algorithme de Dijkstra et le parcours en largeur ?
Si toutes les arêtes ont un poids de 1, l'algorithme de Dijkstra rend les sommets définitifs dans le même ordre que le parcours en largeur. On peut le voir comme une généralisation à des poids différents, qui remplace la file d'attente par une file de priorité renvoyant d'abord la plus petite distance.
Peut-on utiliser l'algorithme de Dijkstra sur des graphes orientés ?
Oui. Tant que les poids sont supérieurs ou égaux à 0, il trouve des plus courts chemins corrects dans les graphes orientés comme non orientés, y compris ceux qui ont des cycles.