Plus courts chemins : Dijkstra
Cours · OCaml (option informatique), chapitre 16 · prépas MPSI et MP, option informatique · le début du chapitre, la suite sur Adloun
16.1 Introduction et motivation
Le parcours en largeur (chapitre 15) trouve le plus court chemin… quand toutes les arêtes « coûtent » pareil. Mais sur un réseau routier, les routes ont des longueurs différentes : le plus court chemin n'est plus celui qui traverse le moins de villes, mais celui dont la somme des distances est minimale. Il faut des graphes pondérés et un algorithme adapté : c'est l'algorithme de Dijkstra, l'un des plus célèbres de l'informatique.
Ce chapitre clôt l'étude des graphes. On y voit pourquoi le BFS échoue sur un graphe pondéré, comment Dijkstra construit les distances minimales depuis une source, pourquoi il exige des poids positifs (avec un contre-exemple), comment reconstruire le chemin, et deux variantes (Floyd-Warshall pour toutes les paires, Bellman-Ford pour les poids négatifs).
Faute de distance infinie en machine, on choisit une constante infini plus grande que toute distance réalisable (par exemple 1_000_000 si les distances restent petites, ou la somme de tous les poids plus un). dist.(v) = infini signifie alors « v pas encore atteint ».
Exercices du chapitre
- Dijkstra corrigé
- Distance entre deux sommets corrigé
- Poids unitaires corrigé
- Le contre-exemple des poids négatifs corrigé
- Reconstruire le chemin corrigé
- Floyd-Warshall (toutes les paires) corrigé