Algoritmo di Bellman-Ford
Ultimo aggiornamento
Bellman-Ford trova il cammino minimo da un nodo sorgente a tutti gli altri nodi e, a differenza di Dijkstra, funziona anche quando alcuni pesi degli archi sono negativi. Procede per rilassamento a forza bruta: scorre ripetutamente tutti gli archi e, se passare per un arco dà una distanza più breve, aggiorna la distanza del nodo di destinazione. Premi play qui sopra per vedere le distanze provvisorie scendere passata dopo passata.
Dopo V - 1 passate su tutti gli archi, ogni cammino minimo (che può avere al massimo V - 1 archi) è stato trovato. Questo lo rende O(V · E): più lento di Dijkstra, ma gestisce i pesi negativi e può rilevare un ciclo di peso negativo (se una V-esima passata rilassa ancora un arco, non esiste un cammino minimo).
Complessità temporale e spaziale
| Misura | Complessità | Note |
|---|---|---|
| Tempo | O(V · E) | V − 1 passate su tutti gli E archi |
| Spazio | O(V) | Una distanza per nodo |
| Pesi negativi | Supportati | Il suo vantaggio principale rispetto a Dijkstra |
| Cicli negativi | Rilevabili | Una V-esima passata che rilassa ne segnala uno |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Imposta la distanza della sorgente a 0 e tutte le altre a infinito. |
| 2 | Ripeti il passo successivo V − 1 volte. |
| 3 | Per ogni arco (u → v, w), controlla se dist[u] + w < dist[v]. |
| 4 | Se sì, rilassalo: imposta dist[v] = dist[u] + w. |
| 5 | Fermati prima se una passata completa non cambia nulla. |
Esempio svolto
Sorgente S su 4 nodi S, A, B, C con gli archi S→A (4), S→B (5), A→C (3), B→A (-3), rilassati in questo ordine. Le distanze partono da S=0 e tutto il resto a ∞:
| Passata | Distanze [S, A, B, C] | Azione |
|---|---|---|
| Inizio | [0, ∞, ∞, ∞] | La distanza della sorgente è 0, tutte le altre sono infinito. |
| 1 | [0, 2, 5, 7] | Rilassa S→A a 4, S→B a 5, A→C a 7, poi B→A abbassa A a 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | Ora A→C migliora C a 2 + 3 = 5; nessun altro arco si rilassa. |
| 3 | [0, 2, 5, 5] | Nessun arco si rilassa, quindi le distanze sono definitive: A costa 2 passando per S→B→A. |
Quando usare Bellman-Ford
| Usalo quando | Evitalo quando |
|---|---|
| I pesi degli archi possono essere negativi. | Tutti i pesi sono non negativi (Dijkstra è più veloce). |
| Devi rilevare i cicli di peso negativo. | Il grafo è enorme e denso: O(V · E) è troppo lento. |
| Il grafo è piccolo o sparso. | Ti serve solo una query da sorgente a destinazione su un grafo grande. |
| Ti serve una base semplice e facile da implementare. | I pesi sono non negativi e la latenza conta. |
Codice Bellman-Ford Algorithm
Un'implementazione di Bellman-Ford Algorithm pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Bellman-Ford Algorithm in 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}")Codice Bellman-Ford Algorithm in 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"));Codice Bellman-Ford Algorithm in 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}Codice Bellman-Ford Algorithm in 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}Codice Bellman-Ford Algorithm in 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}Domande frequenti su Bellman-Ford
Qual è la complessità temporale di Bellman-Ford?
Bellman-Ford richiede tempo
O(V · E): fa V - 1 passate e ogni passata rilassa tutti gli E archi. È più lento del O((V + E) log V) di Dijkstra, ed è il prezzo da pagare per supportare i pesi negativi.Quando conviene usare Bellman-Ford invece di Dijkstra?
Usa Bellman-Ford quando il grafo può avere archi con peso negativo, o quando devi rilevare cicli di peso negativo. Dijkstra è più veloce ma è corretto solo con pesi non negativi. Un uso reale comune è il rilevamento di arbitraggi nel cambio valute, dove i cicli negativi contano.
Come fa Bellman-Ford a rilevare un ciclo negativo?
Dopo le
V - 1 passate di rilassamento, tutti i cammini minimi sono definitivi se non esiste un ciclo negativo. Se un'ulteriore passata riesce ancora a rilassare un arco, allora è raggiungibile un ciclo di peso negativo e i cammini minimi non sono definiti (potresti girare all'infinito abbassando il costo).Qual è la differenza tra Bellman-Ford e Floyd-Warshall?
Bellman-Ford calcola i cammini minimi da una singola sorgente in
O(V · E), mentre Floyd-Warshall calcola i cammini minimi tra tutte le coppie in O(V³). Su un grafo denso, eseguire Bellman-Ford da ogni sorgente costa O(V² · E), quindi Floyd-Warshall di solito è la scelta migliore quando ti servono tutte le coppie. Entrambi gestiscono archi negativi e possono segnalare cicli negativi.Perché Bellman-Ford ha bisogno esattamente di V - 1 passate?
Ogni cammino minimo in un grafo senza cicli negativi usa al massimo
V - 1 archi, perché un cammino che visita più di V nodi deve ripeterne uno. Ogni passata garantisce che almeno un altro arco di ogni cammino minimo venga rilassato correttamente, quindi V - 1 passate bastano a sistemarli tutti. Un equivoco comune è che più passate migliorino il risultato: non succede mai, a meno che non esista un ciclo negativo.Bellman-Ford può fermarsi prima?
Sì. Se una passata completa su tutti gli archi non rilassa nulla, ogni distanza è già ottimale e puoi fermarti prima di arrivare a
V - 1 passate. Questa ottimizzazione di uscita anticipata spesso lo rende molto più veloce sui grafi che convergono in fretta, anche se il limite nel caso peggiore resta O(V · E).Risorse correlate
Altre visualizzazioni
