Bonjour,
Dans nos leçons précédentes, nous avons exploré en profondeur deux algorithmes fondamentaux pour la recherche de plus courts chemins à origine unique : l'algorithme de Dijkstra et celui de Bellman-Ford. Vous avez implémenté Dijkstra, prouvé sa correction sous l'hypothèse de poids non-négatifs, puis implémenté Bellman-Ford en comprenant sa capacité à gérer le cas général, y compris la détection de cycles négatifs.
L'objectif de cette leçon est de synthétiser ces connaissances pour atteindre une maîtrise complète de l'objectif : comparer les cas d'usage et les complexités de Dijkstra et Bellman-Ford. Cette compétence de discernement est essentielle pour l'Agrégation, où l'on attend de vous non seulement la connaissance des algorithmes, mais aussi la capacité à justifier le choix du meilleur outil pour un problème donné.
Nous allons structurer cette comparaison autour de trois axes : le principe algorithmique fondamental, les garanties et les limites, et enfin la performance.
1. Opposition des Paradigmes : Glouton vs. Programmation Dynamique
La différence la plus profonde entre Dijkstra et Bellman-Ford ne réside pas seulement dans leur gestion des poids, mais dans leur paradigme algorithmique sous-jacent.
Dijkstra : L'approche Gloutonne
L'algorithme de Dijkstra est l'archétype de l'algorithme glouton. À chaque étape, il fait un choix qui semble localement optimal : il sélectionne le sommet u non encore finalisé (dans la file de priorité) qui a la plus petite distance estimée depuis la source. Il déclare ce chemin comme étant le plus court et finalise ce sommet. Ce choix est définitif et irrévocable.
Cette stratégie n'est correcte que parce que l'hypothèse des poids non-négatifs garantit qu'un chemin passant par d'autres sommets, nécessairement plus éloignés, ne pourra jamais "rattraper" son retard pour offrir une route plus courte vers u.
Bellman-Ford : L'approche par Programmation Dynamique
L'algorithme de Bellman-Ford s'apparente à la programmation dynamique. Il ne prend aucune décision définitive avant la toute fin. L'idée est de construire la solution itérativement. Après la -ième itération (où une itération consiste à relâcher toutes les arêtes du graphe), l'algorithme a trouvé les plus courts chemins qui utilisent au plus arêtes.
En répétant ce processus fois, il garantit de trouver tous les plus courts chemins simples (sans cycle). Cette approche, moins "pressée", lui permet de réviser ses estimations à chaque passe, et c'est cette capacité de révision qui lui permet de gérer correctement les poids négatifs.
Pour illustrer de manière frappante la faille de l'approche gloutonne, regardons un exemple concret où Dijkstra échoue.
Shortest Path Algorithms Explained (Dijkstra's & Bellman-Ford)
La vidéo suivante montre un scénario où l'ajout d'une seule arête à poids négatif rend la solution de Dijkstra incorrecte. Cet exemple visuel est crucial pour comprendre pourquoi la stratégie gloutonne est inadéquate dans le cas général.
Regardez la section de 05:24 à 07:19. Observez comment Dijkstra, après avoir finalisé le chemin vers le nœud 'e', est incapable de tirer profit d'un chemin plus avantageux qui se révèle plus tard via l'arête négative. Cela illustre parfaitement la rigidité du choix glouton.
2. Tableau Comparatif Synthétique
Pour l'épreuve, avoir une vision claire et structurée des forces et faiblesses de chaque algorithme est primordial. Résumons notre analyse dans un tableau.
| Critère | Algorithme de Dijkstra | Algorithme de Bellman-Ford |
|---|---|---|
| Poids des arêtes | Non-négatifs uniquement () | Gère les poids positifs et négatifs |
| Cycles négatifs | Ne fonctionne pas. Peut donner un résultat erroné ou boucler. Ne les détecte pas. | Détecte les cycles de poids négatif accessibles depuis la source et le signale. |
| Paradigm | Glouton (Greedy) | Programmation dynamique |
| Structure de données | File de priorité (tas binaire, tas de Fibonacci) | Aucune structure de données complexe, simple itération sur les arêtes |
| Complexité Temporelle | **$O( | E |
Cette comparaison est au cœur de nombreux exercices d'algorithmique. La vidéo suivante résume bien la motivation derrière le choix de Bellman-Ford malgré sa complexité supérieure.
Bellman Ford Algorithm | Shortest path & Negative cycles | Graph Theory
Cette courte introduction à Bellman-Ford par WilliamFiset met immédiatement en perspective sa complexité et son principal avantage sur Dijkstra.
Regardez la première minute (00:12 à 01:22). L'auteur y expose clairement le compromis : Bellman-Ford est plus lent, mais il est indispensable lorsque Dijkstra échoue, c'est-à-dire en présence de poids négatifs.
3. Un Cadre de Décision pour l'Agrégation
Face à un problème de plus court chemin, quel algorithme choisir ? Voici une démarche systématique :
-
Analyser les contraintes du graphe : La première question à se poser concerne les poids des arêtes.
- Tous les poids sont-ils positifs ou nuls ?
- Oui : L'algorithme de Dijkstra est le choix par défaut. Il est nettement plus performant.
- Certains poids sont-ils négatifs ?
- Oui : L'algorithme de Dijkstra est inutilisable. Il faut passer à Bellman-Ford.
- Tous les poids sont-ils positifs ou nuls ?
-
Analyser l'objectif du problème :
- Le problème demande-t-il simplement le plus court chemin ?
- Si le graphe peut contenir des poids négatifs, Bellman-Ford donnera la réponse correcte, à condition qu'il n'y ait pas de cycle négatif sur le chemin.
- Le problème demande-t-il de détecter des anomalies ou des opportunités (par ex: arbitrage en finance) ?
- C'est un indice fort pour l'utilisation de Bellman-Ford. Sa capacité à détecter les cycles de poids négatif est une fonctionnalité clé, et non un simple effet de bord.
- Le problème demande-t-il simplement le plus court chemin ?
Le document de préparation à l'Agrégation de l'ENS Paris-Saclay formalise cette distinction.
[PDF] Préparation agrégation : Algorithmique
Ce polycopié, que nous avons déjà utilisé, résume la situation de manière concise en abordant le problème des plus courts chemins pour tout couple de sommets. Sa conclusion est sans appel.
Lisez le paragraphe "Plus courts chemins pour tout couple de sommets". Notez la phrase clé : "Si l’on autorise les arcs de poids négatif, l’algorithme de Dijkstra n’est plus utilisable. Il faut alors exécuter l’algorithme de Bellman-Ford".
Enfin, pour une synthèse parfaite de ce processus de décision, le document du CNRS que nous avons également consulté propose un guide pratique.
[PDF] Quelques rappels sur la théorie des graphes - CNRS
Cette section de synthèse offre un arbre de décision clair et concis pour choisir le bon algorithme de plus court chemin.
Lisez la section 3.2, "Synthèse" (page 18). Portez une attention particulière aux points concernant la recherche d'un plus court chemin dans un graphe avec circuits. Cet encadré est un excellent résumé à mémoriser pour le concours.
Conclusion
Aujourd'hui, nous avons formalisé la comparaison entre Dijkstra et Bellman-Ford, une étape cruciale pour affiner votre jugement algorithmique.
Les points à retenir absolument :
- Dijkstra est un algorithme glouton, rapide (), mais qui exige des poids non-négatifs.
- Bellman-Ford est un algorithme basé sur la programmation dynamique, plus lent (), mais général : il gère les poids négatifs et détecte les cycles négatifs.
- Le choix entre les deux est un arbitrage classique entre performance et généralité. Cet arbitrage est entièrement dicté par les propriétés du graphe (la nature des poids de ses arêtes).
Dans notre prochaine leçon, nous aborderons un autre problème fondamental des graphes : la recherche d'un arbre couvrant de poids minimum (Minimum Spanning Tree). Nous commencerons par l'algorithme de Prim, qui, vous le verrez, présente d'intéressantes similitudes structurelles avec l'algorithme de Dijkstra, tout en résolvant un problème entièrement différent.