- Actuel
- A une distance
- Arête utilisée
- Chemin
- Cycle négatif
Algorithme de Bellman–Ford
L'algorithme de Dijkstra échoue quand une arête a une longueur négative, comme une route qui vous verse un péage au lieu de vous en faire payer un. L'algorithme de Bellman–Ford, non : il examine simplement chaque arête encore et encore jusqu'à ce que plus rien ne s'améliore, et il sait même dire quand un cycle fait baisser les distances sans fin. Cliquez sur un nœud pour partir de lui et avancez passage par passage. Appuyez sur Lecture pour suivre la recherche, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Chaque arête est à sens unique, comme le montre sa flèche, et le nombre dessus est sa longueur, qui peut être négative. Cliquez sur un nœud pour en faire le départ ; basculez le clic sur Cible et cliquez sur un autre nœud pour voir à la fin le plus court chemin jusqu'à lui. Le nombre sur chaque nœud est sa distance jusqu'ici. Cochez Ajouter un cycle négatif pour voir comment Bellman–Ford en trouve un. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Cliquez sur un nœud pour en faire le départ. Pour voir un chemin à la fin, basculez le clic sur Cible et cliquez sur un autre nœud.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
- Cochez Ajouter un cycle négatif pour voir Bellman–Ford en trouver un. Nouveau graphe crée un autre graphe à essayer.
Fonctionnement de Bellman–Ford
Donnez au départ la distance 0 et à tous les autres nœuds l'infini. Puis faites des passages : à chaque passage, examinez une fois chaque arête u → v. Si u a une distance et que dist(u) plus la longueur de l'arête est plus court que dist(v), baissez dist(v) et retenez u comme moyen d'y arriver. Après le passage k, tous les plus courts chemins d'au plus k arêtes sont connus. Un plus court chemin passe au plus une fois par chaque nœud, il a donc au plus n − 1 arêtes, et n − 1 passages suffisent toujours. Si un passage entier ne change rien, la recherche peut s'arrêter tôt.
Trouver un cycle négatif
Si les arêtes d'un cycle totalisent moins que zéro, refaire un tour raccourcit toujours un chemin : il n'y a donc pas de plus court chemin du tout. Bellman–Ford le remarque : après n − 1 passages, un passage de plus ne devrait rien changer. Si une arête peut encore être relâchée, un cycle négatif est accessible depuis le départ, et remonter les nœuds retenus depuis cette arête mène jusqu'à lui. Dans l'application, le cycle est tracé en rouge.
Questions fréquemment posées
Qu'est-ce que l'algorithme de Bellman–Ford ?
Un algorithme qui trouve les plus courts chemins d'un départ vers tous les autres nœuds dans un graphe dont les arêtes peuvent avoir des longueurs négatives. Il relâche chaque arête en passages répétés, et il signale un cycle négatif s'il en existe un accessible depuis le départ.
Pourquoi l'algorithme de Dijkstra échoue-t-il avec des arêtes négatives ?
Dijkstra rend la distance d'un nœud définitive dès qu'il est le plus proche dans la file. Une arête négative trouvée plus tard peut encore ramener à ce nœud par un chemin plus court, donc la distance définitive peut être fausse. Bellman–Ford ne rend jamais une distance définitive trop tôt ; il continue d'examiner chaque arête.
Pourquoi n − 1 passages ?
Un plus court chemin n'a jamais besoin de passer deux fois par un nœud, il a donc au plus n − 1 arêtes. Chaque passage allonge les plus courts chemins connus d'au moins une arête : après n − 1 passages, ils sont donc tous trouvés.
Bellman–Ford est-il rapide ?
Chaque passage examine les E arêtes et il y a au plus V − 1 passages : le travail croît donc en V × E. C'est plus lent que l'algorithme de Dijkstra, c'est pourquoi on utilise Bellman–Ford quand des arêtes peuvent être négatives.
Mon graphe est-il envoyé quelque part ?
Non. Le graphe est créé et parcouru dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur