Algorithme de Dijkstra

Besoin

Algorithme de PCC pour les coûts d'arêtes >= 0 (ou variables).

Analyse

À partir d'un sommet de départ, examiner l'ensemble des nœuds les plus proches, plus l'ensemble des nœuds un niveau plus loin, etc.

Conception

Parcours du graphe depuis une source, en largeur d'abord.

Tout au long du calcul, on maintient 2 ensembles :

• Tant que C, l'ensemble des sommets qui restent à visiter (au départ C=S-départ) n'est pas vide :
  • Pour chaque somme de D, l'ensemble des sommets pour lesquels on connaît déjà leur plus petite distance à la source (au départ, D=départ)
    • on conserve 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...).

Exemples

• Routage internet (OSPF, IS-IS)

Notes

• Complexité en O(a² log(n)) où a est le nombre d'arêtes