Algoritmo di Bellman Ford

L'algoritmo di Bellman Ford ci aiuta a trovare il percorso più breve da un vertice a tutti gli altri vertici di un grafo ponderato.

È simile all'algoritmo di Dijkstra ma può funzionare con grafici in cui gli archi possono avere pesi negativi.

Perché mai si dovrebbero avere bordi con pesi negativi nella vita reale?

I bordi di peso negativi potrebbero sembrare inutili all'inizio, ma possono spiegare molti fenomeni come il flusso di cassa, il calore rilasciato / assorbito in una reazione chimica, ecc.

Ad esempio, se ci sono modi diversi per passare da una sostanza chimica A a un'altra chimica B, ogni metodo avrà sotto-reazioni che coinvolgono sia la dissipazione del calore che l'assorbimento.

Se vogliamo trovare l'insieme di reazioni in cui è richiesta l'energia minima, allora dovremo essere in grado di considerare l'assorbimento di calore come pesi negativi e la dissipazione del calore come pesi positivi.

Perché dobbiamo stare attenti con i pesi negativi?

I bordi di peso negativi possono creare cicli di peso negativi, ovvero un ciclo che ridurrà la distanza totale del percorso tornando allo stesso punto.

I cicli di peso negativo possono dare un risultato errato quando si cerca di trovare il percorso più breve

Gli algoritmi del percorso più breve come l'algoritmo di Dijkstra che non sono in grado di rilevare un tale ciclo possono dare un risultato errato perché possono passare attraverso un ciclo di peso negativo e ridurre la lunghezza del percorso.

Come funziona l'algoritmo di Bellman Ford

L'algoritmo di Bellman Ford funziona sovrastimando la lunghezza del percorso dal vertice iniziale a tutti gli altri vertici. Quindi rilassa in modo iterativo quelle stime trovando nuovi percorsi più brevi di quelli precedentemente sovrastimati.

Facendo questo ripetutamente per tutti i vertici, possiamo garantire che il risultato sia ottimizzato.

Step-1 per l'algoritmo di Bellman Ford Step-2 per l'algoritmo di Bellman Ford Step-3 per l'algoritmo di Bellman Ford Step-4 per l'algoritmo di Bellman Ford Step-5 per l'algoritmo di Bellman Ford Step-6 per l'algoritmo di Bellman Ford

Pseudocodice di Bellman Ford

Dobbiamo mantenere la distanza del percorso di ogni vertice. Possiamo memorizzarlo in un array di dimensione v, dove v è il numero di vertici.

Vogliamo anche essere in grado di ottenere il percorso più breve, non solo conoscere la lunghezza del percorso più breve. Per questo, mappiamo ogni vertice al vertice che ha aggiornato per ultimo la sua lunghezza del percorso.

Una volta che l'algoritmo è finito, possiamo tornare indietro dal vertice di destinazione al vertice di origine per trovare il percorso.

 funzione bellman Ford (G, S) per ogni vertice V in G distanza (V) <- infinito precedente (V) <- NULL distanza (S) <- 0 per ogni vertice V in G per ogni bordo (U, V) in G tempDistance <- distanza (U) + edge_weight (U, V) se tempDistance <distanza (V) distanza (V) <- tempDistance precedente (V) <- U per ogni bordo (U, V) in G If distanza (U) + edge_weight (U, V) <distance (V) Error: Negative Cycle Exists distanza di ritorno (), precedente ()

Bellman Ford contro Dijkstra

L'algoritmo di Bellman Ford e l'algoritmo di Dijkstra hanno una struttura molto simile. Mentre Dijkstra guarda solo agli immediati vicini di un vertice, Bellman passa attraverso ogni bordo in ogni iterazione.

Algoritmo di Dijkstra vs Bellman Ford

Esempi di Python, Java e C / C ++

Python Java C C ++ 
 # Bellman Ford Algorithm in Python class Graph: def __init__(self, vertices): self.V = vertices # Total number of vertices in the graph self.graph = () # Array of edges # Add edges def add_edge(self, s, d, w): self.graph.append((s, d, w)) # Print the solution def print_solution(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("(0) (1)".format(i, dist(i))) def bellman_ford(self, src): # Step 1: fill the distance array and predecessor array dist = (float("Inf")) * self.V # Mark the source vertex dist(src) = 0 # Step 2: relax edges |V| - 1 times for _ in range(self.V - 1): for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): dist(d) = dist(s) + w # Step 3: detect negative cycle # if value changes then we have a negative cycle in the graph # and we cannot find the shortest distances for s, d, w in self.graph: if dist(s) != float("Inf") and dist(s) + w < dist(d): print("Graph contains negative weight cycle") return # No negative weight cycle found! # Print the distance and predecessor array self.print_solution(dist) g = Graph(5) g.add_edge(0, 1, 5) g.add_edge(0, 2, 4) g.add_edge(1, 3, 3) g.add_edge(2, 1, 6) g.add_edge(3, 2, 2) g.bellman_ford(0)
 // Bellman Ford Algorithm in Java class CreateGraph ( // CreateGraph - it consists of edges class CreateEdge ( int s, d, w; CreateEdge() ( s = d = w = 0; ) ); int V, E; CreateEdge edge(); // Creates a graph with V vertices and E edges CreateGraph(int v, int e) ( V = v; E = e; edge = new CreateEdge(e); for (int i = 0; i < e; ++i) edge(i) = new CreateEdge(); ) void BellmanFord(CreateGraph graph, int s) ( int V = graph.V, E = graph.E; int dist() = new int(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; ++i) dist(i) = Integer.MAX_VALUE; // Mark the source vertex dist(s) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i < V; ++i) ( for (int j = 0; j < E; ++j) ( // Get the edge data int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int j = 0; j < E; ++j) ( int u = graph.edge(j).s; int v = graph.edge(j).d; int w = graph.edge(j).w; if (dist(u) != Integer.MAX_VALUE && dist(u) + w < dist(v)) ( System.out.println("CreateGraph contains negative w cycle"); return; ) ) // No negative w cycle found! // Print the distance and predecessor array printSolution(dist, V); ) // Print the solution void printSolution(int dist(), int V) ( System.out.println("Vertex Distance from Source"); for (int i = 0; i 1 graph.edge(0).s = 0; graph.edge(0).d = 1; graph.edge(0).w = 5; // edge 0 --> 2 graph.edge(1).s = 0; graph.edge(1).d = 2; graph.edge(1).w = 4; // edge 1 --> 3 graph.edge(2).s = 1; graph.edge(2).d = 3; graph.edge(2).w = 3; // edge 2 --> 1 graph.edge(3).s = 2; graph.edge(3).d = 1; graph.edge(3).w = 6; // edge 3 --> 2 graph.edge(4).s = 3; graph.edge(4).d = 2; graph.edge(4).w = 2; graph.BellmanFord(graph, 0); // 0 is the source vertex ) )
 // Bellman Ford Algorithm in C #include #include #define INFINITY 99999 //struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //weight of the edge (u,v) ); //Graph - it consists of edges struct Graph ( int V; //total number of vertices in the graph int E; //total number of edges in the graph struct Edge *edge; //array of edges ); void bellmanford(struct Graph *g, int source); void display(int arr(), int size); int main(void) ( //create graph struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph)); g->V = 4; //total vertices g->E = 5; //total edges //array of edges for graph g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge)); //------- adding the edges of the graph /* edge(u, v) where u = start vertex of the edge (u,v) v = end vertex of the edge (u,v) w is the weight of the edge (u,v) */ //edge 0 --> 1 g->edge(0).u = 0; g->edge(0).v = 1; g->edge(0).w = 5; //edge 0 --> 2 g->edge(1).u = 0; g->edge(1).v = 2; g->edge(1).w = 4; //edge 1 --> 3 g->edge(2).u = 1; g->edge(2).v = 3; g->edge(2).w = 3; //edge 2 --> 1 g->edge(3).u = 2; g->edge(3).v = 1; g->edge(3).w = 6; //edge 3 --> 2 g->edge(4).u = 3; g->edge(4).v = 2; g->edge(4).w = 2; bellmanford(g, 0); //0 is the source vertex return 0; ) void bellmanford(struct Graph *g, int source) ( //variables int i, j, u, v, w; //total vertex in the graph g int tV = g->V; //total edge in the graph g int tE = g->E; //distance array //size equal to the number of vertices of the graph g int d(tV); //predecessor array //size equal to the number of vertices of the graph g int p(tV); //step 1: fill the distance array and predecessor array for (i = 0; i < tV; i++) ( d(i) = INFINITY; p(i) = 0; ) //mark the source vertex d(source) = 0; //step 2: relax edges |V| - 1 times for (i = 1; i <= tV - 1; i++) ( for (j = 0; j edge(j).u; v = g->edge(j).v; w = g->edge(j).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( d(v) = d(u) + w; p(v) = u; ) ) ) //step 3: detect negative cycle //if value changes then we have a negative cycle in the graph //and we cannot find the shortest distances for (i = 0; i edge(i).u; v = g->edge(i).v; w = g->edge(i).w; if (d(u) != INFINITY && d(v)> d(u) + w) ( printf("Negative weight cycle detected!"); return; ) ) //No negative weight cycle found! //print the distance and predecessor array printf("Distance array: "); display(d, tV); printf("Predecessor array: "); display(p, tV); ) void display(int arr(), int size) ( int i; for (i = 0; i < size; i++) ( printf("%d ", arr(i)); ) printf(""); )
 // Bellman Ford Algorithm in C++ #include // Struct for the edges of the graph struct Edge ( int u; //start vertex of the edge int v; //end vertex of the edge int w; //w of the edge (u,v) ); // Graph - it consists of edges struct Graph ( int V; // Total number of vertices in the graph int E; // Total number of edges in the graph struct Edge* edge; // Array of edges ); // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) ( struct Graph* graph = new Graph; graph->V = V; // Total Vertices graph->E = E; // Total edges // Array of edges for graph graph->edge = new Edge(E); return graph; ) // Printing the solution void printArr(int arr(), int size) ( int i; for (i = 0; i V; int E = graph->E; int dist(V); // Step 1: fill the distance array and predecessor array for (int i = 0; i < V; i++) dist(i) = INT_MAX; // Mark the source vertex dist(u) = 0; // Step 2: relax edges |V| - 1 times for (int i = 1; i <= V - 1; i++) ( for (int j = 0; j edge(j).u; int v = graph->edge(j).v; int w = graph->edge(j).w; if (dist(u) != INT_MAX && dist(u) + w < dist(v)) dist(v) = dist(u) + w; ) ) // Step 3: detect negative cycle // if value changes then we have a negative cycle in the graph // and we cannot find the shortest distances for (int i = 0; i edge(i).u; int v = graph->edge(i).v; int w = graph->edge(i).w; if (dist(u) != INT_MAX && dist(u) + w 1 graph->edge(0).u = 0; graph->edge(0).v = 1; graph->edge(0).w = 5; //edge 0 --> 2 graph->edge(1).u = 0; graph->edge(1).v = 2; graph->edge(1).w = 4; //edge 1 --> 3 graph->edge(2).u = 1; graph->edge(2).v = 3; graph->edge(2).w = 3; //edge 2 --> 1 graph->edge(3).u = 2; graph->edge(3).v = 1; graph->edge(3).w = 6; //edge 3 --> 2 graph->edge(4).u = 3; graph->edge(4).v = 2; graph->edge(4).w = 2; BellmanFord(graph, 0); //0 is the source vertex return 0; )

Complessità di Bellman Ford

Complessità temporale

Migliore complessità del caso O (E)
Complessità media dei casi O (VE)
Complessità del caso peggiore O (VE)

Complessità spaziale

E la complessità dello spazio è O(V).

Applicazioni dell'algoritmo di Bellman Ford

  1. Per il calcolo dei percorsi più brevi negli algoritmi di instradamento
  2. Per trovare il percorso più breve

Articoli interessanti...