Bellman Ford algoritmusa

A Bellman Ford algoritmus segít megtalálni a legrövidebb utat a csúcstól a súlyozott gráf összes többi csúcsáig.

Hasonló Dijkstra algoritmusához, de képes olyan grafikonokkal dolgozni, amelyek éleinek negatív súlya lehet.

Miért lenne valaha a negatív súlyú élek a való életben?

A negatív súlyélek eleinte haszontalannak tűnhetnek, de sok olyan jelenséget meg tudnak magyarázni, mint a cashflow, a kémiai reakcióban felszabaduló / elnyelt hő stb.

Például, ha különböző módon lehet elérni az egyik A vegyi anyagtól a másik B vegyi anyagig, akkor mindegyik módszer részreakcióval rendelkezik, amelyek hőelvezetést és abszorpciót is magukban foglalnak.

Ha meg akarjuk találni a reakciókészletet, ahol minimális energia szükséges, akkor képesnek kell lennünk a hőfelvételre negatív súlyként, a hőelvezetésre pedig pozitív súlyként.

Miért kell vigyáznunk a negatív súlyokkal?

A negatív súlyélek negatív súlyciklusokat hozhatnak létre, azaz olyan ciklusokat, amelyek csökkentik a teljes pályatávolságot azáltal, hogy visszatérnek ugyanabba a pontba.

A negatív súlyciklusok helytelen eredményt adhatnak, amikor megpróbálják kideríteni a legrövidebb utat

A legrövidebb útvonal-algoritmusok, mint például Dijkstra algoritmusai, amelyek nem képesek kimutatni egy ilyen ciklust, helytelen eredményt adhatnak, mert negatív súlycikluson mennek keresztül és csökkenthetik az út hosszát.

Hogyan működik Bellman Ford algoritmusa

A Bellman Ford algoritmus úgy működik, hogy túlbecsüli az út hosszát a kezdő csúcstól az összes többi csúcsig. Ezután ismételten ellazítja ezeket a becsléseket azáltal, hogy új utakat talál, amelyek rövidebbek, mint a korábban túlbecsült utak.

Ha ezt minden csúcsnál többször elvégezzük, garantálhatjuk az eredmény optimalizálását.

Step-1 a Bellman Ford algoritmusához

Step-2 a Bellman Ford algoritmusához

Step-3 a Bellman Ford algoritmusához

Step-4 a Bellman Ford algoritmusához

Step-5 a Bellman Ford algoritmusához Step-5 a Bellman Ford algoritmusához

Step-6 a Bellman Ford algoritmusához Step-6

Bellman Ford álkód

Fenn kell tartanunk minden csúcs elérési útját. Ezt tárolhatjuk egy v méretű tömbben, ahol v a csúcsok száma.

Szeretnénk a legrövidebb utat is megkapni, nem csak a legrövidebb út hosszát. Ehhez minden csúcsot leképezünk arra a csúcsra, amely utoljára frissítette útvonalának hosszát.

Miután az algoritmus véget ért, visszaléphetünk a célcsúcsról a forráscsúcsra, hogy megtaláljuk az utat.

 függvény bellmanFord (G, S) minden V csúcsra G távolságban (V) <- végtelen előző (V) <- NULL távolság (S) <- 0 minden V csúcsra G-ben minden élre (U, V) G-ben tempDistance <- távolság (U) + él_súly (U, V), ha tempDistance <távolság (V) távolság (V) <- tempDistance előző (V) <- U minden élre (U, V) G-ban, ha távolság (U) + él_súly (U, V) <távolság (V) Hiba: Negatív ciklus visszatérési távolság (), előző ()

Bellman Ford vs Dijkstra

Bellman Ford algoritmusa és Dijkstra algoritmusa nagyon hasonló felépítésű. Míg Dijkstra csak egy csúcs közvetlen szomszédaira néz, Bellman minden iterációban végigmegy az egyes éleken.

Dijkstra vs Bellman Ford algoritmusa

Példák Python, Java és 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 komplexitása

Az idő komplexitása

Legjobb eset komplexitás	O (E)
Átlagos esetösszetétel	O (VE)
Legrosszabb eset komplexitás	O (VE)

Tér komplexitás

És a tér bonyolultsága az O(V).