Der Bellman-Ford-Algorithmus ist ein Single-Source-Shortest-Path-Algorithmus. Dieser Algorithmus wird verwendet, um den kürzesten Abstand vom einzelnen Scheitelpunkt zu allen anderen Scheitelpunkten eines gewichteten Diagramms zu ermitteln. Es gibt verschiedene andere Algorithmen, die verwendet werden, um den kürzesten Weg zu finden, wie der Dijkstra-Algorithmus usw. Wenn der gewichtete Graph negative Gewichtswerte enthält, bestätigt der Dijkstra-Algorithmus nicht, ob er die richtige Antwort liefert oder nicht. Im Gegensatz zum Dijkstra-Algorithmus garantiert der Bellman-Ford-Algorithmus die richtige Antwort, selbst wenn der gewichtete Graph negative Gewichtswerte enthält.
Regel dieses Algorithmus
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Betrachten Sie die folgende Grafik:
Wie wir in der obigen Grafik sehen können, sind einige der Gewichte negativ. Das obige Diagramm enthält 6 Eckpunkte, daher werden wir bis zu den 5 Eckpunkten weiter entspannen. Hier werden wir alle Kanten fünfmal entspannen. Die Schleife wird fünfmal durchlaufen, um die richtige Antwort zu erhalten. Wenn die Schleife mehr als fünf Mal wiederholt wird, ist auch die Antwort dieselbe, d. h. der Abstand zwischen den Eckpunkten ändert sich nicht.
Entspannen bedeutet:
Java Mathe.min
If (d(u) + c(u , v) <d(v)) d(v)="d(u)" + c(u , v) < pre> <p>To find the shortest path of the above graph, the first step is note down all the edges which are given below:</p> <p>(A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B)</p> <p>Let's consider the source vertex as 'A'; therefore, the distance value at vertex A is 0 and the distance value at all the other vertices as infinity shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-2.webp" alt="Bellman-Ford Algorithm"> <p>Since the graph has six vertices so it will have five iterations.</p> <p> <strong>First iteration</strong> </p> <p>Consider the edge (A, B). Denote vertex 'A' as 'u' and vertex 'B' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 6</p> <p>Since (0 + 6) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 6 = 6</p> <p>Therefore, the distance of vertex B is 6.</p> <p>Consider the edge (A, C). Denote vertex 'A' as 'u' and vertex 'C' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 4</p> <p>Since (0 + 4) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 4 = 4</p> <p>Therefore, the distance of vertex C is 4.</p> <p>Consider the edge (A, D). Denote vertex 'A' as 'u' and vertex 'D' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 5</p> <p>Since (0 + 5) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 5 = 5</p> <p>Therefore, the distance of vertex D is 5.</p> <p>Consider the edge (B, E). Denote vertex 'B' as 'u' and vertex 'E' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 6</p> <p>d(v) = ∞</p> <p>c(u , v) = -1</p> <p>Since (6 - 1) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 6 - 1= 5</p> <p>Therefore, the distance of vertex E is 5.</p> <p>Consider the edge (C, E). Denote vertex 'C' as 'u' and vertex 'E' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 4</p> <p>d(v) = 5</p> <p>c(u , v) = 3</p> <p>Since (4 + 3) is greater than 5, so there will be no updation. The value at vertex E is 5.</p> <p>Consider the edge (D, C). Denote vertex 'D' as 'u' and vertex 'C' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 5</p> <p>d(v) = 4</p> <p>c(u , v) = -2</p> <p>Since (5 -2) is less than 4, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 5 - 2 = 3</p> <p>Therefore, the distance of vertex C is 3.</p> <p>Consider the edge (D, F). Denote vertex 'D' as 'u' and vertex 'F' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 5</p> <p>d(v) = ∞</p> <p>c(u , v) = -1</p> <p>Since (5 -1) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 5 - 1 = 4</p> <p>Therefore, the distance of vertex F is 4.</p> <p>Consider the edge (E, F). Denote vertex 'E' as 'u' and vertex 'F' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 5</p> <p>d(v) = ∞</p> <p>c(u , v) = 3</p> <p>Since (5 + 3) is greater than 4, so there would be no updation on the distance value of vertex F.</p> <p>Consider the edge (C, B). Denote vertex 'C' as 'u' and vertex 'B' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 3</p> <p>d(v) = 6</p> <p>c(u , v) = -2</p> <p>Since (3 - 2) is less than 6, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 3 - 2 = 1</p> <p>Therefore, the distance of vertex B is 1.</p> <p>Now the first iteration is completed. We move to the second iteration.</p> <p> <strong>Second iteration:</strong> </p> <p>In the second iteration, we again check all the edges. The first edge is (A, B). Since (0 + 6) is greater than 1 so there would be no updation in the vertex B.</p> <p>The next edge is (A, C). Since (0 + 4) is greater than 3 so there would be no updation in the vertex C.</p> <p>The next edge is (A, D). Since (0 + 5) equals to 5 so there would be no updation in the vertex D.</p> <p>The next edge is (B, E). Since (1 - 1) equals to 0 which is less than 5 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(E) = d(B) +c(B , E)</p> <p>= 1 - 1 = 0</p> <p>The next edge is (C, E). Since (3 + 3) equals to 6 which is greater than 5 so there would be no updation in the vertex E.</p> <p>The next edge is (D, C). Since (5 - 2) equals to 3 so there would be no updation in the vertex C.</p> <p>The next edge is (D, F). Since (5 - 1) equals to 4 so there would be no updation in the vertex F.</p> <p>The next edge is (E, F). Since (5 + 3) equals to 8 which is greater than 4 so there would be no updation in the vertex F.</p> <p>The next edge is (C, B). Since (3 - 2) equals to 1` so there would be no updation in the vertex B.</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-3.webp" alt="Bellman-Ford Algorithm"> <p> <strong>Third iteration</strong> </p> <p>We will perform the same steps as we did in the previous iterations. We will observe that there will be no updation in the distance of vertices.</p> <pre> The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3 </pre> <p> <strong>Time Complexity</strong> </p> <p>The time complexity of Bellman ford algorithm would be O(E|V| - 1).</p> <pre> function bellmanFord(G, S) for each vertex V in G distance[V] <- 0 infinite previous[v] <- null distance[s] for each vertex v in g edge (u,v) tempdistance distance[u] + edge_weight(u, v) if < distance[v] u distance[v} error: negative cycle exists return distance[], previous[] pre> <p> <strong>Drawbacks of Bellman ford algorithm</strong> </p> <ul> <li>The bellman ford algorithm does not produce a correct answer if the sum of the edges of a cycle is negative. Let's understand this property through an example. Consider the below graph. <br> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-4.webp" alt="Bellman-Ford Algorithm"></li> <li>In the above graph, we consider vertex 1 as the source vertex and provides 0 value to it. We provide infinity value to other vertices shown as below: <br> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-5.webp" alt="Bellman-Ford Algorithm"> <br>Edges can be written as: <br> (1, 3), (1, 2), (2, 4), (3, 2), (4, 3) </li> </ul> <p> <strong>First iteration</strong> </p> <p> <strong>Consider the edge (1, 3). Denote vertex '1' as 'u' and vertex '3' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 5</p> <p>Since (0 + 5) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 5 = 5</p> <p>Therefore, the distance of vertex 3 is 5.</p> <p> <strong>Consider the edge (1, 2). Denote vertex '1' as 'u' and vertex '2' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 4</p> <p>Since (0 + 4) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 4 = 4</p> <p>Therefore, the distance of vertex 2 is 4.</p> <p> <strong>Consider the edge (3, 2). Denote vertex '3' as 'u' and vertex '2' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 5</p> <p>d(v) = 4</p> <p>c(u , v) = 7</p> <p>Since (5 + 7) is greater than 4, so there would be no updation in the vertex 2.</p> <p> <strong>Consider the edge (2, 4). Denote vertex '2' as 'u' and vertex '4' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 4</p> <p>d(v) = ∞</p> <p>c(u , v) = 7</p> <p>Since (4 + 7) equals to 11 which is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 4 + 7 = 11</p> <p>Therefore, the distance of vertex 4 is 11.</p> <p> <strong>Consider the edge (4, 3). Denote vertex '4' as 'u' and vertex '3' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 11</p> <p>d(v) = 5</p> <p>c(u , v) = -15</p> <p>Since (11 - 15) equals to -4 which is less than 5, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 11 - 15 = -4</p> <p>Therefore, the distance of vertex 3 is -4.</p> <p>Now we move to the second iteration.</p> <p> <strong>Second iteration</strong> </p> <p>Now, again we will check all the edges. The first edge is (1, 3). Since (0 + 5) equals to 5 which is greater than -4 so there would be no updation in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) equals to 4 so there would be no updation in the vertex 2.</p> <p>The next edge is (3, 2). Since (-4 + 7) equals to 3 which is less than 4 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -4 + 7 = 3</p> <p>Therefore, the value at vertex 2 is 3.</p> <p>The next edge is (2, 4). Since ( 3+7) equals to 10 which is less than 11 so update</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(4) = d(2) +c(2, 4)</p> <p>= 3 + 7 = 10</p> <p>Therefore, the value at vertex 4 is 10.</p> <p>The next edge is (4, 3). Since (10 - 15) equals to -5 which is less than -4 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(3) = d(4) +c(4, 3)</p> <p>= 10 - 15 = -5</p> <p>Therefore, the value at vertex 3 is -5.</p> <p>Now we move to the third iteration.</p> <p> <strong>Third iteration</strong> </p> <p>Now again we will check all the edges. The first edge is (1, 3). Since (0 + 5) equals to 5 which is greater than -5 so there would be no updation in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) equals to 4 which is greater than 3 so there would be no updation in the vertex 2.</p> <p>The next edge is (3, 2). Since (-5 + 7) equals to 2 which is less than 3 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -5 + 7 = 2</p> <p>Therefore, the value at vertex 2 is 2.</p> <p>The next edge is (2, 4). Since (2 + 7) equals to 9 which is less than 10 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(4) = d(2) +c(2, 4)</p> <p>= 2 + 7 = 9</p> <p>Therefore, the value at vertex 4 is 9.</p> <p>The next edge is (4, 3). Since (9 - 15) equals to -6 which is less than -5 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(3) = d(4) +c(4, 3)</p> <p>= 9 - 15 = -6</p> <p>Therefore, the value at vertex 3 is -6.</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-6.webp" alt="Bellman-Ford Algorithm"> <p>Since the graph contains 4 vertices, so according to the bellman ford algorithm, there would be only 3 iterations. If we try to perform 4<sup>th</sup> iteration on the graph, the distance of the vertices from the given vertex should not change. If the distance varies, it means that the bellman ford algorithm is not providing the correct answer.</p> <p> <strong>4<sup>th</sup> iteration</strong> </p> <p>The first edge is (1, 3). Since (0 +5) equals to 5 which is greater than -6 so there would be no change in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) is greater than 2 so there would be no updation.</p> <p>The next edge is (3, 2). Since (-6 + 7) equals to 1 which is less than 3 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -6 + 7 = 1</p> <p>In this case, the value of the vertex is updated. So, we conclude that the bellman ford algorithm does not work when the graph contains the negative weight cycle.</p> <p>Therefore, the value at vertex 2 is 1.</p> <hr></-></pre></d(v))>
d(v) = 0 + 6 = 6
Daher beträgt der Abstand des Scheitelpunkts B 6.
Betrachten Sie die Kante (A, C). Bezeichnen Sie den Scheitelpunkt „A“ als „u“ und den Scheitelpunkt „C“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Da (0 + 4) kleiner als ∞ ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Daher beträgt der Abstand des Scheitelpunkts C 4.
Betrachten Sie die Kante (A, D). Bezeichnen Sie den Scheitelpunkt „A“ als „u“ und den Scheitelpunkt „D“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Da (0 + 5) kleiner als ∞ ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Daher beträgt der Abstand des Scheitelpunkts D 5.
Betrachten Sie die Kante (B, E). Bezeichnen Sie den Scheitelpunkt „B“ als „u“ und den Scheitelpunkt „E“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Da (6 - 1) kleiner als ∞ ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 6 - 1= 5
Daher beträgt der Abstand des Scheitelpunkts E 5.
Betrachten Sie die Kante (C, E). Bezeichnen Sie den Scheitelpunkt „C“ als „u“ und den Scheitelpunkt „E“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 4
d(v) = 5
c(u, v) = 3
Da (4 + 3) größer als 5 ist, findet keine Aktualisierung statt. Der Wert am Scheitelpunkt E beträgt 5.
Betrachten Sie die Kante (D, C). Bezeichnen Sie den Scheitelpunkt „D“ als „u“ und den Scheitelpunkt „C“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 5
d(v) = 4
c(u, v) = -2
Da (5 -2) kleiner als 4 ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Daher beträgt der Abstand des Scheitelpunkts C 3.
Betrachten Sie die Kante (D, F). Bezeichnen Sie den Scheitelpunkt „D“ als „u“ und den Scheitelpunkt „F“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Da (5 -1) kleiner als ∞ ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Daher beträgt der Abstand des Scheitelpunkts F 4.
Betrachten Sie die Kante (E, F). Bezeichnen Sie den Scheitelpunkt „E“ als „u“ und den Scheitelpunkt „F“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Da (5 + 3) größer als 4 ist, würde der Abstandswert des Scheitelpunkts F nicht aktualisiert.
Betrachten Sie die Kante (C, B). Bezeichnen Sie den Scheitelpunkt „C“ als „u“ und den Scheitelpunkt „B“ als „v“. Nutzen Sie nun die Entspannungsformel:
bestes Lächeln der Welt
d(u) = 3
d(v) = 6
c(u, v) = -2
Da (3 - 2) kleiner als 6 ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Daher beträgt der Abstand des Scheitelpunkts B 1.
Nun ist die erste Iteration abgeschlossen. Wir gehen zur zweiten Iteration über.
Zweite Iteration:
In der zweiten Iteration überprüfen wir erneut alle Kanten. Die erste Kante ist (A, B). Da (0 + 6) größer als 1 ist, würde es im Scheitelpunkt B keine Aktualisierung geben.
Die nächste Kante ist (A, C). Da (0 + 4) größer als 3 ist, würde es im Scheitelpunkt C keine Aktualisierung geben.
Die nächste Kante ist (A, D). Da (0 + 5) gleich 5 ist, würde es im Scheitelpunkt D keine Aktualisierung geben.
Die nächste Kante ist (B, E). Da (1 - 1) gleich 0 ist, was kleiner als 5 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
Die nächste Kante ist (C, E). Da (3 + 3) gleich 6 ist, was größer als 5 ist, würde es im Scheitelpunkt E keine Aktualisierung geben.
Die nächste Kante ist (D, C). Da (5 - 2) gleich 3 ist, würde es im Scheitelpunkt C keine Aktualisierung geben.
Die nächste Kante ist (D, F). Da (5 - 1) gleich 4 ist, würde es im Scheitelpunkt F keine Aktualisierung geben.
Die nächste Kante ist (E, F). Da (5 + 3) gleich 8 ist, was größer als 4 ist, würde es im Scheitelpunkt F keine Aktualisierung geben.
Die nächste Kante ist (C, B). Da (3 - 2) gleich 1` ist, würde es im Scheitelpunkt B keine Aktualisierung geben.
Dritte Iteration
Wir werden die gleichen Schritte wie in den vorherigen Iterationen ausführen. Wir werden feststellen, dass der Abstand der Eckpunkte nicht aktualisiert wird.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Zeitkomplexität
Die zeitliche Komplexität des Bellman-Ford-Algorithmus wäre O(E|V| - 1).
function bellmanFord(G, S) for each vertex V in G distance[V] <- 0 infinite previous[v] <- null distance[s] for each vertex v in g edge (u,v) tempdistance distance[u] + edge_weight(u, v) if < distance[v] u distance[v} error: negative cycle exists return distance[], previous[] pre> <p> <strong>Drawbacks of Bellman ford algorithm</strong> </p> <ul> <li>The bellman ford algorithm does not produce a correct answer if the sum of the edges of a cycle is negative. Let's understand this property through an example. Consider the below graph. <br> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-4.webp" alt="Bellman-Ford Algorithm"></li> <li>In the above graph, we consider vertex 1 as the source vertex and provides 0 value to it. We provide infinity value to other vertices shown as below: <br> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-5.webp" alt="Bellman-Ford Algorithm"> <br>Edges can be written as: <br> (1, 3), (1, 2), (2, 4), (3, 2), (4, 3) </li> </ul> <p> <strong>First iteration</strong> </p> <p> <strong>Consider the edge (1, 3). Denote vertex '1' as 'u' and vertex '3' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 5</p> <p>Since (0 + 5) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 5 = 5</p> <p>Therefore, the distance of vertex 3 is 5.</p> <p> <strong>Consider the edge (1, 2). Denote vertex '1' as 'u' and vertex '2' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 4</p> <p>Since (0 + 4) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 4 = 4</p> <p>Therefore, the distance of vertex 2 is 4.</p> <p> <strong>Consider the edge (3, 2). Denote vertex '3' as 'u' and vertex '2' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 5</p> <p>d(v) = 4</p> <p>c(u , v) = 7</p> <p>Since (5 + 7) is greater than 4, so there would be no updation in the vertex 2.</p> <p> <strong>Consider the edge (2, 4). Denote vertex '2' as 'u' and vertex '4' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 4</p> <p>d(v) = ∞</p> <p>c(u , v) = 7</p> <p>Since (4 + 7) equals to 11 which is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 4 + 7 = 11</p> <p>Therefore, the distance of vertex 4 is 11.</p> <p> <strong>Consider the edge (4, 3). Denote vertex '4' as 'u' and vertex '3' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 11</p> <p>d(v) = 5</p> <p>c(u , v) = -15</p> <p>Since (11 - 15) equals to -4 which is less than 5, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 11 - 15 = -4</p> <p>Therefore, the distance of vertex 3 is -4.</p> <p>Now we move to the second iteration.</p> <p> <strong>Second iteration</strong> </p> <p>Now, again we will check all the edges. The first edge is (1, 3). Since (0 + 5) equals to 5 which is greater than -4 so there would be no updation in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) equals to 4 so there would be no updation in the vertex 2.</p> <p>The next edge is (3, 2). Since (-4 + 7) equals to 3 which is less than 4 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -4 + 7 = 3</p> <p>Therefore, the value at vertex 2 is 3.</p> <p>The next edge is (2, 4). Since ( 3+7) equals to 10 which is less than 11 so update</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(4) = d(2) +c(2, 4)</p> <p>= 3 + 7 = 10</p> <p>Therefore, the value at vertex 4 is 10.</p> <p>The next edge is (4, 3). Since (10 - 15) equals to -5 which is less than -4 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(3) = d(4) +c(4, 3)</p> <p>= 10 - 15 = -5</p> <p>Therefore, the value at vertex 3 is -5.</p> <p>Now we move to the third iteration.</p> <p> <strong>Third iteration</strong> </p> <p>Now again we will check all the edges. The first edge is (1, 3). Since (0 + 5) equals to 5 which is greater than -5 so there would be no updation in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) equals to 4 which is greater than 3 so there would be no updation in the vertex 2.</p> <p>The next edge is (3, 2). Since (-5 + 7) equals to 2 which is less than 3 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -5 + 7 = 2</p> <p>Therefore, the value at vertex 2 is 2.</p> <p>The next edge is (2, 4). Since (2 + 7) equals to 9 which is less than 10 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(4) = d(2) +c(2, 4)</p> <p>= 2 + 7 = 9</p> <p>Therefore, the value at vertex 4 is 9.</p> <p>The next edge is (4, 3). Since (9 - 15) equals to -6 which is less than -5 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(3) = d(4) +c(4, 3)</p> <p>= 9 - 15 = -6</p> <p>Therefore, the value at vertex 3 is -6.</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-6.webp" alt="Bellman-Ford Algorithm"> <p>Since the graph contains 4 vertices, so according to the bellman ford algorithm, there would be only 3 iterations. If we try to perform 4<sup>th</sup> iteration on the graph, the distance of the vertices from the given vertex should not change. If the distance varies, it means that the bellman ford algorithm is not providing the correct answer.</p> <p> <strong>4<sup>th</sup> iteration</strong> </p> <p>The first edge is (1, 3). Since (0 +5) equals to 5 which is greater than -6 so there would be no change in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) is greater than 2 so there would be no updation.</p> <p>The next edge is (3, 2). Since (-6 + 7) equals to 1 which is less than 3 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -6 + 7 = 1</p> <p>In this case, the value of the vertex is updated. So, we conclude that the bellman ford algorithm does not work when the graph contains the negative weight cycle.</p> <p>Therefore, the value at vertex 2 is 1.</p> <hr></->
d(v) = 0 + 5 = 5
Daher beträgt der Abstand von Scheitelpunkt 3 5.
Betrachten Sie die Kante (1, 2). Bezeichnen Sie Scheitelpunkt „1“ als „u“ und Scheitelpunkt „2“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Da (0 + 4) kleiner als ∞ ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Daher beträgt der Abstand von Scheitelpunkt 2 4.
Betrachten Sie die Kante (3, 2). Bezeichnen Sie Scheitelpunkt „3“ als „u“ und Scheitelpunkt „2“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 5
d(v) = 4
c(u, v) = 7
Da (5 + 7) größer als 4 ist, würde es im Scheitelpunkt 2 keine Aktualisierung geben.
Betrachten Sie die Kante (2, 4). Bezeichnen Sie Scheitelpunkt „2“ als „u“ und Scheitelpunkt „4“ als „v“. Nutzen Sie nun die Entspannungsformel:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Da (4 + 7) gleich 11 ist, was kleiner als ∞ ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Daher beträgt der Abstand von Scheitelpunkt 4 11.
Betrachten Sie die Kante (4, 3). Bezeichnen Sie Scheitelpunkt „4“ als „u“ und Scheitelpunkt „3“ als „v“. Nutzen Sie nun die Entspannungsformel:
C-Programm zum String-Vergleich
d(u) = 11
d(v) = 5
c(u, v) = -15
Da (11 - 15) gleich -4 ist, was weniger als 5 ist, aktualisieren Sie es
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Daher beträgt der Abstand von Scheitelpunkt 3 -4.
Jetzt gehen wir zur zweiten Iteration über.
Zweite Iteration
Jetzt überprüfen wir noch einmal alle Kanten. Die erste Kante ist (1, 3). Da (0 + 5) gleich 5 ist, was größer als -4 ist, würde es im Scheitelpunkt 3 keine Aktualisierung geben.
Die nächste Kante ist (1, 2). Da (0 + 4) gleich 4 ist, würde es im Scheitelpunkt 2 keine Aktualisierung geben.
Die nächste Kante ist (3, 2). Da (-4 + 7) gleich 3 ist, was weniger als 4 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Daher beträgt der Wert am Scheitelpunkt 2 3.
Die nächste Kante ist (2, 4). Da (3+7) gleich 10 ist, was weniger als 11 ist, aktualisieren Sie es
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Daher beträgt der Wert am Scheitelpunkt 4 10.
PD-Zusammenführung
Die nächste Kante ist (4, 3). Da (10 - 15) gleich -5 ist, was kleiner als -4 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Daher beträgt der Wert am Scheitelpunkt 3 -5.
Jetzt gehen wir zur dritten Iteration über.
Dritte Iteration
Jetzt werden wir noch einmal alle Kanten überprüfen. Die erste Kante ist (1, 3). Da (0 + 5) gleich 5 ist, was größer als -5 ist, würde es im Scheitelpunkt 3 keine Aktualisierung geben.
Die nächste Kante ist (1, 2). Da (0 + 4) gleich 4 ist, was größer als 3 ist, würde es im Scheitelpunkt 2 keine Aktualisierung geben.
Die nächste Kante ist (3, 2). Da (-5 + 7) gleich 2 ist, was weniger als 3 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Daher ist der Wert am Scheitelpunkt 2 2.
Die nächste Kante ist (2, 4). Da (2 + 7) gleich 9 ist, was weniger als 10 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Daher beträgt der Wert am Scheitelpunkt 4 9.
Die nächste Kante ist (4, 3). Da (9 - 15) gleich -6 ist, was kleiner als -5 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Daher beträgt der Wert am Scheitelpunkt 3 -6.
Da der Graph 4 Eckpunkte enthält, gäbe es nach dem Bellman-Ford-Algorithmus nur 3 Iterationen. Wenn wir versuchen, 4 durchzuführenThBei der Iteration im Diagramm sollte sich der Abstand der Scheitelpunkte vom angegebenen Scheitelpunkt nicht ändern. Wenn der Abstand variiert, bedeutet dies, dass der Bellman-Ford-Algorithmus nicht die richtige Antwort liefert.
4ThWiederholung
Die erste Kante ist (1, 3). Da (0 +5) gleich 5 ist, was größer als -6 ist, würde sich der Scheitelpunkt 3 nicht ändern.
Die nächste Kante ist (1, 2). Da (0 + 4) größer als 2 ist, erfolgt keine Aktualisierung.
Die nächste Kante ist (3, 2). Da (-6 + 7) gleich 1 ist, was kleiner als 3 ist, aktualisieren Sie Folgendes:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
In diesem Fall wird der Wert des Scheitelpunkts aktualisiert. Daraus schließen wir, dass der Bellman-Ford-Algorithmus nicht funktioniert, wenn der Graph den negativen Gewichtszyklus enthält.
Daher ist der Wert am Scheitelpunkt 2 1.