MPE51 Algorithme de Dijkstra

[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

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)

 

Une réflexion sur « MPE51 Algorithme de Dijkstra »

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *