Algorithme de Bellman-Ford
Dernière mise à jour
Bellman-Ford trouve le plus court chemin d'un nœud source vers tous les autres nœuds et, contrairement à Dijkstra, il fonctionne même lorsque certains poids d'arête sont négatifs. Il procède par relâchement en force brute : il balaie de façon répétée chaque arête et, si passer par cette arête donne une distance plus courte, il met à jour la distance du nœud cible. Appuyez sur lecture ci-dessus pour voir les distances provisoires diminuer passe après passe.
Après V - 1 passes sur toutes les arêtes, chaque plus court chemin (qui peut avoir au plus V - 1 arêtes) a été trouvé. Cela le rend O(V · E) - plus lent que Dijkstra, mais il gère les poids négatifs et peut détecter un cycle de poids négatif (si une V-ième passe relâche encore une arête, aucun plus court chemin n'existe).
Complexité en temps et en espace
| Mesure | Complexité | Notes |
|---|---|---|
| Temps | O(V · E) | V − 1 passes sur toutes les E arêtes |
| Espace | O(V) | Une distance par nœud |
| Poids négatifs | Pris en charge | Son avantage clé sur Dijkstra |
| Cycles négatifs | Détectables | Une V-ième passe qui relâche en signale un |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Fixez la distance de la source à 0 et toutes les autres à l'infini. |
| 2 | Répétez l'étape suivante V − 1 fois. |
| 3 | Pour chaque arête (u → v, w), vérifiez si dist[u] + w < dist[v]. |
| 4 | Si oui, relâchez-la : posez dist[v] = dist[u] + w. |
| 5 | Arrêtez plus tôt si une passe complète ne change rien. |
Exemple résolu
Source S sur 4 nœuds S, A, B, C avec les arêtes S→A (4), S→B (5), A→C (3), B→A (-3), relâchées dans cet ordre. Les distances commencent à S=0 et tout le reste à ∞ :
| Passe | Distances [S, A, B, C] | Action |
|---|---|---|
| Init | [0, ∞, ∞, ∞] | La distance de la source est 0, toutes les autres l'infini. |
| 1 | [0, 2, 5, 7] | Relâche S→A à 4, S→B à 5, A→C à 7, puis B→A abaisse A à 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | A→C améliore désormais C à 2 + 3 = 5 ; aucune autre arête ne se relâche. |
| 3 | [0, 2, 5, 5] | Aucune arête ne se relâche, donc les distances sont définitives : A coûte 2 via S→B→A. |
Quand utiliser Bellman-Ford
| À utiliser quand | À éviter quand |
|---|---|
| Les poids d'arête peuvent être négatifs. | Tous les poids sont non négatifs (Dijkstra est plus rapide). |
| Vous devez détecter des cycles de poids négatif. | Le graphe est énorme et dense - O(V · E) est trop lent. |
| Le graphe est petit ou creux. | Vous n'avez besoin que d'une requête source-cible sur un grand graphe. |
| Vous voulez une base simple et facile à implémenter. | Les poids sont non négatifs et la latence compte. |
Code de Bellman-Ford Algorithm
Une implémentation propre et exécutable de Bellman-Ford Algorithm en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Bellman-Ford Algorithm en Python
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Code de Bellman-Ford Algorithm en JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Code de Bellman-Ford Algorithm en Java
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Code de Bellman-Ford Algorithm en C++
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Code de Bellman-Ford Algorithm en C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}FAQ Bellman-Ford
Quelle est la complexité temporelle de Bellman-Ford ?
Bellman-Ford s'exécute en temps
O(V · E) : il fait V - 1 passes, et chaque passe relâche les E arêtes. C'est plus lent que le O((V + E) log V) de Dijkstra, ce qui est le prix de la prise en charge des poids d'arête négatifs.Quand utiliser Bellman-Ford plutôt que Dijkstra ?
Utilisez Bellman-Ford lorsque le graphe peut avoir des poids d'arête négatifs, ou lorsque vous devez détecter des cycles de poids négatif. Dijkstra est plus rapide mais n'est correct qu'avec des poids non négatifs. Un usage réel courant est la détection d'arbitrage de change, où les cycles négatifs comptent.
Comment Bellman-Ford détecte-t-il un cycle négatif ?
Après les
V - 1 passes de relâchement, tous les plus courts chemins sont finalisés s'il n'existe aucun cycle négatif. Si une passe de plus peut encore relâcher une arête, alors un cycle de poids négatif est atteignable, et les plus courts chemins sont indéfinis (vous pourriez boucler à l'infini pour réduire le coût).Quelle est la différence entre Bellman-Ford et Floyd-Warshall ?
Bellman-Ford calcule les plus courts chemins depuis une source unique en
O(V · E), tandis que Floyd-Warshall calcule les plus courts chemins entre toutes les paires en O(V³). Sur un graphe dense, exécuter Bellman-Ford depuis chaque source coûte O(V² · E), donc Floyd-Warshall est généralement le meilleur choix quand vous avez besoin de toutes les paires. Les deux gèrent les arêtes négatives et peuvent signaler les cycles négatifs.Pourquoi Bellman-Ford a-t-il besoin d'exactement V - 1 passes ?
Tout plus court chemin dans un graphe sans cycle négatif utilise au plus
V - 1 arêtes, car un chemin visitant plus de V nœuds doit en répéter un. Chaque passe garantit qu'au moins une arête de plus de chaque plus court chemin est relâchée correctement, donc V - 1 passes suffisent à les fixer toutes. Une idée fausse courante est que plus de passes améliorent le résultat - elles ne le font jamais, sauf s'il existe un cycle négatif.Bellman-Ford peut-il s'arrêter plus tôt ?
Oui. Si une passe complète sur toutes les arêtes ne relâche rien, toutes les distances sont déjà optimales et vous pouvez vous arrêter avant d'atteindre les
V - 1 passes. Cette optimisation de sortie anticipée le rend souvent bien plus rapide sur les graphes qui convergent vite, même si la borne du pire cas reste O(V · E).Ressources associées
Plus de visualisations
