PLOT. Nouvelle série. N° 46. p. 18-22. Le problème du plus court chemin : une présentation de l’algorithme de Dijkstra.

Une version texte intégral est en téléchargement sur le site Bibliothèque numérique des IREM et de l’APMEP Télécharger

Auteur : Boyer Germain

Résumé

Cet article expose une présentation de l’algorithme de Dijkstra qui apporte une réponse au problème du voyageur de commerce.
Il traite différents cas à travers des exemples. Il propose une écriture de l’algorithme en langage naturel qui permet de traiter le cas où il y a plusieurs solutions en introduisant la possibilité qu’un sommet soit visité plusieurs fois pendant le déroulement de l’algorithme mais une seule fois par le voyageur de commerce. La présentation et l’algorithme proposés permettent de suivre pas à pas sur le graphe les étapes du parcours du plus court chemin.

Notes

Cet article est publié sous la rubrique « Sortons des sentiers battus ».

PLOT (Partager, Lire, Ouvrir, Transmettre) est une revue de l’APMEP. Créée en 1976 par trois Régionales (Poitiers, Limoges, Orléans-Tours), la revue a connu deux périodes : la première en tant que revue régionale (numéros 1 à 103) ; la seconde en tant que revue nationale de 2003 à 2017 : PLOT Nouvelle série (numéros 1 à 60). La publication s’arrête en 2017 à la création de Au Fil des Maths – le bulletin de l’APMEP.
PLOT était un trimestriel, permettant aux collègues de lire des articles proches du « terrain » (complémentaires de ceux du Bulletin de l’APMEP dit Bulletin Vert) s’appuyant sur des pratiques réelles et souvent innovantes, des comptes rendus et analyses d’activités. En incitant à une réflexion de fond, ces articles permettent de prendre du recul par rapport aux habitudes quotidiennes de professeurs de mathématiques. Cette revue, que l’équipe de rédaction destinait plus particulièrement aux professeurs débutants, s’avère aussi utile aux nombreux collègues soucieux de la qualité de leur enseignement.

Données de publication

Éditeur Association des Professeurs de Mathématiques de l’Enseignement Public (APMEP) Paris , 2014 Format A4, p. 18-22
ISSN 0397-7471

Public visé enseignant Niveau lycée, terminale Âge 17

Type article de périodique ou revue Langue français Support papier