En théorie des graphes, l'algorithme de Dijkstra (prononcer [dɛjkstra]) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer le plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Il s'applique à un graphe connexe dont le poids lié aux arêtes est positif ou nul.
L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra et a été publié en 19591.
Aucun commentaire:
Enregistrer un commentaire