[Avant-dernier article issu de notre projet Ma petite encyclipédie, il est consacré à l’algorithme de Dijkstra, très utilisé pour trouver le chemin le plus court d’un point à un autre.
Bon week-end à tous !]
Algorithme de Dijkstra
Algorithme permettant de résoudre le problème du plus court chemin.
Etant donné un graphe orienté pondéré par des nombre réels positifs, il calcule le plus court chemin entre deux sommets.
Cet algorithme est très utile pour le calcul des itinéraires routiers ou des itinéraires utilisant les transports en commun mais il est également utilisé pour résoudre des problèmes de routages sur Internet.
Vidéo d’Yvan Monka montrant le fonctionnement de l’algorithme:
Pour en savoir plus
Bibliographie
GAYRAUD T., AUTHIÉ G., UNIVERSITÉ TOULOUSE 3 PAUL SABATIER (1969-….). Contribution à la résolution de problèmes d’optimisation dans les graphes par des algorithmes parallèles. S.l : [s.n], 1992.
LEVITIN A. Introduction to the design & analysis of algorithms. Boston; Montréal : Pearson / Addison-Wesley, 2012. ISBN : 978-0-13-231681-1.
merci d’avoir evoqué Eugene Grasset dans votre article sur Georges Peignot !