Algorithmes de Dijkstra, Prim et Kruskal⚓︎
Intentions⚓︎
Introduction
Dans ce chapitre, on présente deux grandes applications pratiques des graphes :
- le problème du plus court chemin dans un graphe connexe valué simple avec l'algortihme de Dijkstra ;
- la détermination d'un arbre couvrant minimal dans un graphe connexe non orienté valué et simple avec les algorithmes de Prim et Kruskal.
Déroulé
On propose le déroulé suivant :
- un point de cours interactif présentant ces deux problèmes et les illustrant sur des exemples simples « à la main » ;
- des exercices d'entraînement pour manipuler ces différents algorithmes sur des exemples simples.
Cours⚓︎
Cours
Exercices
Ressources⚓︎
Il n'y a pas de ressources associées à ce chapitre.