Spé. TES

Plus court chemin dans un graphe pondéré connexe

Objectifs du programme

L'enseignement de spécialité prend appui sur la résolution de problèmes. […] Plusieurs exemples de problèmes sont donnés à titre indicatif.

L'étude de telles situations conduit à un travail de modélisation et place les élèves en position de recherche.

Les thèmes abordés sont particulièrement propices […] à la mise en œuvre d'algorithmes.

Les graphes […] apparaissent comme des outils pour résoudre des problèmes.

Exemples de problèmes

Minimisation d'une grandeur (coût, longueur, durée, etc.).

Contenu

  • Recherche du plus court chemin sur un graphe pondéré connexe.
Lionel Avon