Bellman ford-algoritmen är en enkällas algoritm för kortaste vägen. Denna algoritm används för att hitta det kortaste avståndet från den enda hörn till alla andra hörn i en viktad graf. Det finns olika andra algoritmer som används för att hitta den kortaste vägen som Dijkstra-algoritmen, etc. Om den viktade grafen innehåller negativa viktvärden, bekräftar inte Dijkstra-algoritmen om den ger rätt svar eller inte. I motsats till Dijkstra-algoritmen garanterar bellman ford-algoritmen rätt svar även om den viktade grafen innehåller de negativa viktvärdena.
Regel för denna algoritm
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Tänk på nedanstående graf:
Som vi kan observera i grafen ovan att vissa av vikterna är negativa. Ovanstående graf innehåller 6 hörn så vi kommer att fortsätta slappna av till de 5 hörnen. Här kommer vi att slappna av alla kanter 5 gånger. Slingan kommer att upprepas 5 gånger för att få rätt svar. Om slingan itereras mer än 5 gånger kommer också svaret att vara detsamma, det vill säga det skulle inte bli någon förändring i avståndet mellan hörnen.
Avkopplande betyder:
java nollkontroll
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
Därför är avståndet för vertex B 6.
Tänk på kanten (A, C). Beteckna vertex 'A' som 'u' och vertex 'C' som 'v'. Använd nu den avslappnande formeln:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Eftersom (0 + 4) är mindre än ∞, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Därför är avståndet för vertex C 4.
Tänk på kanten (A, D). Beteckna vertex 'A' som 'u' och vertex 'D' som 'v'. Använd nu den avslappnande formeln:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Eftersom (0 + 5) är mindre än ∞, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Därför är avståndet för vertex D 5.
Tänk på kanten (B, E). Beteckna vertex 'B' som 'u' och vertex 'E' som 'v'. Använd nu den avslappnande formeln:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Eftersom (6 - 1) är mindre än ∞, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Därför är avståndet till vertex E 5.
Tänk på kanten (C, E). Beteckna vertex 'C' som 'u' och vertex 'E' som 'v'. Använd nu den avslappnande formeln:
d(u) = 4
d(v) = 5
c(u, v) = 3
Eftersom (4 + 3) är större än 5, så blir det ingen uppdatering. Värdet vid hörn E är 5.
Tänk på kanten (D, C). Beteckna vertex 'D' som 'u' och vertex 'C' som 'v'. Använd nu den avslappnande formeln:
d(u) = 5
d(v) = 4
c(u, v) = -2
Eftersom (5 -2) är mindre än 4, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Därför är avståndet till vertex C 3.
Tänk på kanten (D, F). Beteckna vertex 'D' som 'u' och vertex 'F' som 'v'. Använd nu den avslappnande formeln:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Eftersom (5 -1) är mindre än ∞, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Därför är avståndet för vertex F 4.
Tänk på kanten (E, F). Beteckna vertex 'E' som 'u' och vertex 'F' som 'v'. Använd nu den avslappnande formeln:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Eftersom (5 + 3) är större än 4, så skulle det inte bli någon uppdatering av avståndsvärdet för vertex F.
Tänk på kanten (C, B). Beteckna vertex 'C' som 'u' och vertex 'B' som 'v'. Använd nu den avslappnande formeln:
returnerar arrayer i java
d(u) = 3
d(v) = 6
c(u, v) = -2
Eftersom (3 - 2) är mindre än 6, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Därför är avståndet för vertex B 1.
Nu är den första iterationen klar. Vi går till den andra iterationen.
Andra iterationen:
I den andra iterationen kontrollerar vi igen alla kanter. Den första kanten är (A, B). Eftersom (0 + 6) är större än 1 så skulle det inte bli någon uppdatering i vertex B.
Nästa kant är (A, C). Eftersom (0 + 4) är större än 3 så skulle det inte bli någon uppdatering i vertex C.
Nästa kant är (A, D). Eftersom (0 + 5) är lika med 5 så skulle det inte bli någon uppdatering i vertex D.
Nästa kant är (B, E). Eftersom (1 - 1) är lika med 0 vilket är mindre än 5 så uppdatera:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
= 1 - 1 = 0
Nästa kant är (C, E). Eftersom (3 + 3) är lika med 6 som är större än 5 så skulle det inte bli någon uppdatering i vertex E.
Nästa kant är (D, C). Eftersom (5 - 2) är lika med 3 så skulle det inte bli någon uppdatering i vertex C.
Nästa kant är (D, F). Eftersom (5 - 1) är lika med 4 så skulle det inte bli någon uppdatering i vertex F.
Nästa kant är (E, F). Eftersom (5 + 3) är lika med 8 som är större än 4 så skulle det inte bli någon uppdatering i vertex F.
Nästa kant är (C, B). Eftersom (3 - 2) är lika med 1` så skulle det inte bli någon uppdatering i vertex B.
Tredje iterationen
Vi kommer att utföra samma steg som vi gjorde i de tidigare iterationerna. Vi kommer att observera att det inte kommer att ske någon uppdatering i avståndet mellan hörn.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Tidskomplexitet
Tidskomplexiteten för Bellman Ford-algoritmen skulle vara 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
Därför är avståndet för vertex 3 5.
Tänk på kanten (1, 2). Beteckna vertex '1' som 'u' och vertex '2' som 'v'. Använd nu den avslappnande formeln:
rohit shetty skådespelare
d(u) = 0
d(v) = ∞
c(u, v) = 4
Eftersom (0 + 4) är mindre än ∞, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Därför är avståndet för vertex 2 4.
Tänk på kanten (3, 2). Ange vertex '3' som 'u' och vertex '2' som 'v'. Använd nu den avslappnande formeln:
d(u) = 5
d(v) = 4
c(u, v) = 7
Eftersom (5 + 7) är större än 4, så skulle det inte bli någon uppdatering i vertex 2.
Tänk på kanten (2, 4). Beteckna vertex '2' som 'u' och vertex '4' som 'v'. Använd nu den avslappnande formeln:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Eftersom (4 + 7) är lika med 11 vilket är mindre än ∞, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Därför är avståndet för vertex 4 11.
Tänk på kanten (4, 3). Beteckna vertex '4' som 'u' och vertex '3' som 'v'. Använd nu den avslappnande formeln:
d(u) = 11
d(v) = 5
c(u, v) = -15
Eftersom (11 - 15) är lika med -4 vilket är mindre än 5, så uppdatera
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Därför är avståndet för vertex 3 -4.
Nu går vi till den andra iterationen.
Andra iterationen
Nu ska vi återigen kontrollera alla kanter. Den första kanten är (1, 3). Eftersom (0 + 5) är lika med 5 som är större än -4 så skulle det inte bli någon uppdatering i vertex 3.
Nästa kant är (1, 2). Eftersom (0 + 4) är lika med 4 så skulle det inte bli någon uppdatering i vertex 2.
Nästa kant är (3, 2). Eftersom (-4 + 7) är lika med 3 vilket är mindre än 4 så uppdatera:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Därför är värdet vid vertex 2 3.
Nästa kant är (2, 4). Eftersom ( 3+7) är lika med 10 vilket är mindre än 11 så uppdatera
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Därför är värdet vid vertex 4 10.
java karta
Nästa kant är (4, 3). Eftersom (10 - 15) är lika med -5 vilket är mindre än -4 så uppdatera:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Därför är värdet vid vertex 3 -5.
Nu går vi till den tredje iterationen.
Tredje iterationen
Nu ska vi igen kolla alla kanter. Den första kanten är (1, 3). Eftersom (0 + 5) är lika med 5 som är större än -5 så skulle det inte bli någon uppdatering i vertex 3.
Nästa kant är (1, 2). Eftersom (0 + 4) är lika med 4 som är större än 3 så skulle det inte bli någon uppdatering i vertex 2.
Nästa kant är (3, 2). Eftersom (-5 + 7) är lika med 2 vilket är mindre än 3 så uppdatera:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Därför är värdet vid vertex 2 2.
Nästa kant är (2, 4). Eftersom (2 + 7) är lika med 9 vilket är mindre än 10 så uppdatera:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Därför är värdet vid vertex 4 9.
Nästa kant är (4, 3). Eftersom (9 - 15) är lika med -6 vilket är mindre än -5 så uppdatera:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Därför är värdet vid vertex 3 -6.
Eftersom grafen innehåller 4 hörn, så enligt bellman ford-algoritmen, skulle det bara finnas 3 iterationer. Om vi försöker utföra 4thiteration på grafen, bör avståndet mellan hörnen från det givna hörnet inte ändras. Om avståndet varierar betyder det att bellman ford-algoritmen inte ger rätt svar.
4thiteration
Den första kanten är (1, 3). Eftersom (0 +5) är lika med 5 som är större än -6 så skulle det inte bli någon förändring i vertex 3.
Nästa kant är (1, 2). Eftersom (0 + 4) är större än 2 så skulle det inte bli någon uppdatering.
Nästa kant är (3, 2). Eftersom (-6 + 7) är lika med 1 vilket är mindre än 3 så uppdatera:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
I det här fallet uppdateras värdet på vertexet. Så vi drar slutsatsen att bellman ford-algoritmen inte fungerar när grafen innehåller den negativa viktcykeln.
Därför är värdet vid vertex 2 1.