Algorithme de Dijkstra
INFORMATIQUE > ALGORITHMIQUE
Du nom de son inventeur §Edsger 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.
Le plus court chemin d’imposition des multinationales: application de l’algorithme de Dijkstra [En ligne]. [s.l.] : [s.n.], 2015. Disponible sur : < http://hdl.handle.net/2078.1/thesis:2614 > (consulté le 8 mai 2020)