Ο αλγόριθμος Bellman Ford μας βοηθά να βρούμε τη συντομότερη διαδρομή από μια κορυφή προς όλες τις άλλες κορυφές ενός σταθμισμένου γραφήματος.
Είναι παρόμοιο με τον αλγόριθμο Dijkstra, αλλά μπορεί να λειτουργήσει με γραφήματα στα οποία τα άκρα μπορούν να έχουν αρνητικά βάρη.
Γιατί να έχει κανείς άκρα με αρνητικά βάρη στην πραγματική ζωή;
Αρνητικά άκρα βάρους μπορεί να φαίνονται άχρηστα στην αρχή, αλλά μπορούν να εξηγήσουν πολλά φαινόμενα όπως η ταμειακή ροή, η θερμότητα που απελευθερώνεται / απορροφάται σε μια χημική αντίδραση κ.λπ.
Για παράδειγμα, εάν υπάρχουν διαφορετικοί τρόποι για να φτάσετε από το ένα χημικό στο άλλο χημικό Β, κάθε μέθοδος θα έχει υπο-αντιδράσεις που περιλαμβάνουν τόσο την απαγωγή θερμότητας όσο και την απορρόφηση.
Εάν θέλουμε να βρούμε το σύνολο των αντιδράσεων όπου απαιτείται ελάχιστη ενέργεια, τότε θα πρέπει να είμαστε σε θέση να συντελέσουμε στην απορρόφηση θερμότητας ως αρνητικά βάρη και στην απαγωγή θερμότητας ως θετικά βάρη.
Γιατί πρέπει να είμαστε προσεκτικοί με αρνητικά βάρη;
Τα άκρα αρνητικού βάρους μπορούν να δημιουργήσουν κύκλους αρνητικού βάρους, δηλαδή έναν κύκλο που θα μειώσει τη συνολική απόσταση διαδρομής επιστρέφοντας στο ίδιο σημείο.
Οι αρνητικοί κύκλοι βάρους μπορούν να δώσουν ένα λανθασμένο αποτέλεσμα όταν προσπαθείτε να ανακαλύψετε τη συντομότερη διαδρομή
Οι μικρότεροι αλγόριθμοι διαδρομής όπως ο Αλγόριθμος της Dijkstra που δεν είναι σε θέση να ανιχνεύσουν έναν τέτοιο κύκλο, μπορούν να δώσουν ένα λανθασμένο αποτέλεσμα, επειδή μπορούν να περάσουν από έναν αρνητικό κύκλο βάρους και να μειώσουν το μήκος της διαδρομής.
Πώς λειτουργεί ο αλγόριθμος της Bellman Ford
Ο αλγόριθμος Bellman Ford λειτουργεί υπερεκτιμώντας το μήκος της διαδρομής από την αρχική κορυφή προς όλες τις άλλες κορυφές. Στη συνέχεια, χαλαρώνει επαναληπτικά αυτές τις εκτιμήσεις, βρίσκοντας νέες διαδρομές που είναι μικρότερες από τις προηγούμενες εκτιμήσεις.
Κάνοντας αυτό επανειλημμένα για όλες τις κορυφές, μπορούμε να εγγυηθούμε ότι το αποτέλεσμα είναι βελτιστοποιημένο.
Βήμα-1 για τον αλγόριθμο της Bellman Ford 
Βήμα-2 για τον αλγόριθμο 
της Bellman Ford 
Βήμα-1 για τον αλγόριθμο 
της Bellman Ford 
Βήμα-1 για τον αλγόριθμο της Bellman Ford
Bellman Ford Ψευδοκώδικας
Πρέπει να διατηρήσουμε την απόσταση διαδρομής κάθε κορυφής. Μπορούμε να το αποθηκεύσουμε σε μια σειρά μεγέθους v, όπου v είναι ο αριθμός των κορυφών.
Θέλουμε επίσης να έχουμε τη συντομότερη διαδρομή, όχι μόνο να γνωρίζουμε το μήκος της συντομότερης διαδρομής. Για αυτό, χαρτογραφούμε κάθε κορυφή στην κορυφή που ενημερώθηκε τελευταία φορά το μήκος της διαδρομής της.
Μόλις τελειώσει ο αλγόριθμος, μπορούμε να επιστρέψουμε από την κορυφή προορισμού στην κορυφή πηγής για να βρούμε τη διαδρομή.
συνάρτηση bellmanFord (G, S) για κάθε κορυφή V σε απόσταση G (V) <- απεριόριστη προηγούμενη (V) <- απόσταση NULL (S) <- 0 για κάθε κορυφή V σε G για κάθε άκρη (U, V) σε G tempDistance <- απόσταση (U) + edge_weight (U, V) εάν tempDistance <απόσταση (V) απόσταση (V) <- tempDistance προηγούμενο (V) <- U για κάθε άκρο (U, V) σε G Εάν η απόσταση (U) + edge_weight (U, V) <απόσταση (V) Σφάλμα: Αρνητικός κύκλος Υπάρχει απόσταση επιστροφής (), προηγούμενη ()
Μπέλμαν Φορντ vs Ντιζκστρά
Ο αλγόριθμος Bellman Ford και ο αλγόριθμος Dijkstra είναι πολύ παρόμοιοι στη δομή. Ενώ η Dijkstra κοιτάζει μόνο τους άμεσους γείτονες μιας κορυφής, ο Bellman περνά από κάθε άκρη σε κάθε επανάληψη.
Ο Αλγόριθμος της Dijkstra έναντι του Bellman Ford
Παραδείγματα Python, Java και 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; )
Η πολυπλοκότητα του Bellman Ford
Χρόνος πολυπλοκότητας
| Καλύτερη πολυπλοκότητα περιπτώσεων | Ο (Ε) |
| Μέση περίπλοκη περίπτωση | O (VE) |
| Χειρότερη περίπλοκη περίπτωση | O (VE) |
Διαστημική πολυπλοκότητα
Και, η διαστημική πολυπλοκότητα είναι O(V).
Εφαρμογές αλγορίθμου Bellman Ford
- Για τον υπολογισμό των συντομότερων διαδρομών σε αλγόριθμους δρομολόγησης
- Για να βρείτε την πιο σύντομη διαδρομή
