Motivation

Dijkstra développe un ensemble de sommets dont la distance la plus courte est déjà connue. Il finalise toujours le sommet le plus proche qui n'a pas encore été finalisé, puis l'utilise pour améliorer (relâcher) les distances vers ses voisins.

Pourquoi apprendre Dijkstra ?

• Partout : routage GPS, routage de paquets réseau et toute recherche de chemin à moindre coût.
• Glouton qui fonctionne : un exemple clair d'un choix glouton qui donne de manière prouvée l'optimum, tant que les poids sont non négatifs.
• Fondation : son idée de relâchement réapparaît dans A* et d'autres algorithmes de plus court chemin.

Important : Dijkstra suppose l'absence de poids négatifs. Les arêtes négatives nécessitent Bellman-Ford, le prochain cours.