Het Bellman Ford-algoritme is een kortste-padalgoritme uit één bron. Dit algoritme wordt gebruikt om de kortste afstand van het enkele hoekpunt tot alle andere hoekpunten van een gewogen grafiek te vinden. Er zijn verschillende andere algoritmen die worden gebruikt om het kortste pad te vinden, zoals het Dijkstra-algoritme, enz. Als de gewogen grafiek de negatieve gewichtswaarden bevat, bevestigt het Dijkstra-algoritme niet of het het juiste antwoord oplevert of niet. In tegenstelling tot het Dijkstra-algoritme garandeert het Bellman Ford-algoritme het juiste antwoord, zelfs als de gewogen grafiek de negatieve gewichtswaarden bevat.
Regel van dit algoritme
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Beschouw de onderstaande grafiek:
Zoals we in de bovenstaande grafiek kunnen zien, zijn sommige gewichten negatief. De bovenstaande grafiek bevat 6 hoekpunten, dus we zullen doorgaan met ontspannen tot de 5 hoekpunten. Hier zullen we alle randen 5 keer ontspannen. De lus herhaalt zich 5 keer om het juiste antwoord te krijgen. Als de lus meer dan vijf keer wordt herhaald, zal het antwoord ook hetzelfde zijn, d.w.z. er zou geen verandering zijn in de afstand tussen de hoekpunten.
Ontspannen betekent:
distributieve wet booleaanse algebra
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
Daarom is de afstand van hoekpunt B 6.
Beschouw de rand (A, C). Geef hoekpunt 'A' aan als 'u' en hoekpunt 'C' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Omdat (0 + 4) kleiner is dan ∞, updaten dus
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Daarom is de afstand van hoekpunt C 4.
Beschouw de rand (A, D). Geef hoekpunt 'A' aan als 'u' en hoekpunt 'D' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Omdat (0 + 5) kleiner is dan ∞, updaten dus
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Daarom is de afstand van hoekpunt D 5.
Beschouw de rand (B, E). Geef hoekpunt 'B' aan als 'u' en hoekpunt 'E' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Omdat (6 - 1) kleiner is dan ∞, updaten dus
d(v) = d(u) + c(u , v)
d(v) = 6 - 1= 5
Daarom is de afstand van hoekpunt E 5.
Beschouw de rand (C, E). Geef hoekpunt 'C' aan als 'u' en hoekpunt 'E' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 4
d(v) = 5
c(u, v) = 3
Omdat (4 + 3) groter is dan 5, zal er dus geen update plaatsvinden. De waarde bij hoekpunt E is 5.
Beschouw de rand (D, C). Geef hoekpunt 'D' aan als 'u' en hoekpunt 'C' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 5
d(v) = 4
c(u, v) = -2
Omdat (5 -2) kleiner is dan 4, dus update
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Daarom is de afstand van hoekpunt C 3.
Beschouw de rand (D, F). Geef hoekpunt 'D' aan als 'u' en hoekpunt 'F' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Omdat (5 -1) kleiner is dan ∞, updaten dus
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Daarom is de afstand van hoekpunt F 4.
Beschouw de rand (E, F). Geef hoekpunt 'E' aan als 'u' en hoekpunt 'F' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 5
d(v) = ∞
c(u, v) = 3
als anders als java
Omdat (5 + 3) groter is dan 4, zou er dus geen update zijn van de afstandswaarde van hoekpunt F.
Beschouw de rand (C, B). Geef hoekpunt 'C' aan als 'u' en hoekpunt 'B' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 3
d(v) = 6
c(u, v) = -2
Omdat (3 - 2) kleiner is dan 6, dus update
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Daarom is de afstand van hoekpunt B 1.
Nu is de eerste iteratie voltooid. We gaan naar de tweede iteratie.
Tweede iteratie:
In de tweede iteratie controleren we opnieuw alle randen. De eerste rand is (A, B). Omdat (0 + 6) groter is dan 1, zou er geen update plaatsvinden in hoekpunt B.
De volgende rand is (A, C). Omdat (0 + 4) groter is dan 3, zou er dus geen update zijn in hoekpunt C.
De volgende rand is (A, D). Omdat (0 + 5) gelijk is aan 5, zou er dus geen update plaatsvinden in hoekpunt D.
De volgende rand is (B, E). Omdat (1 - 1) gelijk is aan 0, wat kleiner is dan 5, update dus:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
= 1 - 1 = 0
De volgende rand is (C, E). Omdat (3 + 3) gelijk is aan 6, wat groter is dan 5, zou er dus geen update zijn in het hoekpunt E.
De volgende rand is (D, C). Omdat (5 - 2) gelijk is aan 3, zou er dus geen update zijn in hoekpunt C.
De volgende rand is (D, F). Omdat (5 - 1) gelijk is aan 4, zou er dus geen update zijn in het hoekpunt F.
De volgende rand is (E, F). Omdat (5 + 3) gelijk is aan 8, wat groter is dan 4, zou er dus geen update zijn in het hoekpunt F.
De volgende rand is (C, B). Omdat (3 - 2) gelijk is aan 1`, zou er dus geen update zijn in hoekpunt B.
Derde iteratie
We zullen dezelfde stappen uitvoeren als in de vorige iteraties. We zullen zien dat er geen verandering zal optreden in de afstand van de hoekpunten.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Tijdcomplexiteit
De tijdscomplexiteit van het Bellman Ford-algoritme zou O(E|V| - 1) zijn.
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
Daarom is de afstand van hoekpunt 3 5.
Beschouw de rand (1, 2). Geef hoekpunt '1' aan als 'u' en hoekpunt '2' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Omdat (0 + 4) kleiner is dan ∞, updaten dus
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Daarom is de afstand van hoekpunt 2 4.
Beschouw de rand (3, 2). Geef hoekpunt '3' aan als 'u' en hoekpunt '2' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 5
d(v) = 4
c(u, v) = 7
Omdat (5 + 7) groter is dan 4, zou er dus geen update zijn in hoekpunt 2.
Beschouw de rand (2, 4). Geef hoekpunt '2' aan als 'u' en hoekpunt '4' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Omdat (4 + 7) gelijk is aan 11, wat kleiner is dan ∞, dus update
tekenreeks vergelijken c#
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Daarom is de afstand van hoekpunt 4 11.
Beschouw de rand (4, 3). Geef hoekpunt '4' aan als 'u' en hoekpunt '3' als 'v'. Gebruik nu de ontspannende formule:
d(u) = 11
d(v) = 5
c(u, v) = -15
Omdat (11 - 15) gelijk is aan -4, wat minder is dan 5, dus update
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Daarom is de afstand van hoekpunt 3 -4.
Nu gaan we naar de tweede iteratie.
Tweede iteratie
Nu zullen we opnieuw alle randen controleren. De eerste rand is (1, 3). Omdat (0 + 5) gelijk is aan 5, wat groter is dan -4, zou er dus geen update zijn in hoekpunt 3.
De volgende rand is (1, 2). Omdat (0 + 4) gelijk is aan 4, zou er dus geen update zijn in hoekpunt 2.
De volgende rand is (3, 2). Omdat (-4 + 7) gelijk is aan 3, wat minder is dan 4, dus update:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Daarom is de waarde bij hoekpunt 2 3.
De volgende rand is (2, 4). Omdat ( 3+7) gelijk is aan 10, wat minder is dan 11, dus update
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Daarom is de waarde bij hoekpunt 4 10.
Java-tekenreeks bevat
De volgende rand is (4, 3). Omdat (10 - 15) gelijk is aan -5, wat kleiner is dan -4, dus update:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Daarom is de waarde bij hoekpunt 3 -5.
Nu gaan we naar de derde iteratie.
Derde iteratie
Nu zullen we opnieuw alle randen controleren. De eerste rand is (1, 3). Omdat (0 + 5) gelijk is aan 5, wat groter is dan -5, zou er dus geen update zijn in hoekpunt 3.
De volgende rand is (1, 2). Omdat (0 + 4) gelijk is aan 4, wat groter is dan 3, zou er dus geen update zijn in hoekpunt 2.
De volgende rand is (3, 2). Omdat (-5 + 7) gelijk is aan 2, wat minder is dan 3, dus update:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Daarom is de waarde bij hoekpunt 2 2.
De volgende rand is (2, 4). Omdat (2 + 7) gelijk is aan 9, wat minder is dan 10, update dus:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Daarom is de waarde bij hoekpunt 4 9.
De volgende rand is (4, 3). Omdat (9 - 15) gelijk is aan -6, wat kleiner is dan -5, dus update:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Daarom is de waarde bij hoekpunt 3 -6.
Omdat de grafiek vier hoekpunten bevat, zouden er volgens het Bellman Ford-algoritme slechts drie iteraties zijn. Als we proberen 4eiteratie op de grafiek, mag de afstand van de hoekpunten tot het gegeven hoekpunt niet veranderen. Als de afstand varieert, betekent dit dat het Bellman Ford-algoritme niet het juiste antwoord geeft.
4eiteratie
De eerste rand is (1, 3). Omdat (0 +5) gelijk is aan 5, wat groter is dan -6, zou er dus geen verandering zijn in hoekpunt 3.
De volgende rand is (1, 2). Omdat (0 + 4) groter is dan 2, zou er geen update plaatsvinden.
De volgende rand is (3, 2). Omdat (-6 + 7) gelijk is aan 1, wat minder is dan 3, dus update:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
In dit geval wordt de waarde van het hoekpunt bijgewerkt. We concluderen dus dat het Bellman Ford-algoritme niet werkt als de grafiek de negatieve gewichtscyclus bevat.
Daarom is de waarde bij hoekpunt 2 1.