Bellman ford-algoritmen er en algoritme for den korteste vej med en enkelt kilde. Denne algoritme bruges til at finde den korteste afstand fra det enkelte toppunkt til alle de andre toppunkter i en vægtet graf. Der er forskellige andre algoritmer, der bruges til at finde den korteste vej som Dijkstra-algoritmen osv. Hvis den vægtede graf indeholder de negative vægtværdier, bekræfter Dijkstra-algoritmen ikke, om den giver det rigtige svar eller ej. I modsætning til Dijkstra-algoritmen garanterer bellman ford-algoritmen det rigtige svar, selvom den vægtede graf indeholder de negative vægtværdier.
Reglen for denne algoritme
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Overvej nedenstående graf:
Som vi kan observere i ovenstående graf, er nogle af vægtene negative. Ovenstående graf indeholder 6 toppunkter, så vi vil fortsætte med at slappe af indtil de 5 toppunkter. Her vil vi slappe af alle kanter 5 gange. Løkken vil gentage 5 gange for at få det rigtige svar. Hvis løkken itereres mere end 5 gange, vil svaret også være det samme, dvs. der ville ikke være nogen ændring i afstanden mellem hjørnerne.
Afslappende betyder:
java har næste
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
Derfor er afstanden til toppunktet B 6.
Overvej kanten (A, C). Angiv toppunkt 'A' som 'u' og toppunkt 'C' som 'v'. Brug nu den afslappende formel:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Da (0 + 4) er mindre end ∞, så opdater
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Derfor er afstanden til toppunktet C 4.
Overvej kanten (A, D). Angiv toppunkt 'A' som 'u' og toppunkt 'D' som 'v'. Brug nu den afslappende formel:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Da (0 + 5) er mindre end ∞, så opdater
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Derfor er afstanden til toppunktet D 5.
Overvej kanten (B, E). Angiv toppunkt 'B' som 'u' og toppunkt 'E' som 'v'. Brug nu den afslappende formel:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Da (6 - 1) er mindre end ∞, så opdater
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Derfor er afstanden til toppunktet E 5.
Overvej kanten (C, E). Angiv toppunkt 'C' som 'u' og toppunkt 'E' som 'v'. Brug nu den afslappende formel:
d(u) = 4
d(v) = 5
c(u, v) = 3
Da (4 + 3) er større end 5, vil der ikke være nogen opdatering. Værdien ved toppunktet E er 5.
Overvej kanten (D, C). Angiv toppunkt 'D' som 'u' og toppunkt 'C' som 'v'. Brug nu den afslappende formel:
d(u) = 5
d(v) = 4
c(u, v) = -2
Da (5 -2) er mindre end 4, så opdater
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Derfor er afstanden til toppunktet C 3.
Overvej kanten (D, F). Angiv toppunkt 'D' som 'u' og toppunkt 'F' som 'v'. Brug nu den afslappende formel:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Da (5 -1) er mindre end ∞, så opdater
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Derfor er afstanden til toppunktet F 4.
Overvej kanten (E, F). Angiv toppunkt 'E' som 'u' og toppunkt 'F' som 'v'. Brug nu den afslappende formel:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Da (5 + 3) er større end 4, så ville der ikke være nogen opdatering af afstandsværdien af toppunkt F.
Overvej kanten (C, B). Angiv toppunkt 'C' som 'u' og toppunkt 'B' som 'v'. Brug nu den afslappende formel:
d(u) = 3
d(v) = 6
c(u, v) = -2
Da (3 - 2) er mindre end 6, så opdater
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Derfor er afstanden til toppunktet B 1.
Nu er den første iteration afsluttet. Vi går videre til anden iteration.
Anden iteration:
I den anden iteration kontrollerer vi igen alle kanterne. Den første kant er (A, B). Da (0 + 6) er større end 1, ville der ikke være nogen opdatering i toppunktet B.
Den næste kant er (A, C). Da (0 + 4) er større end 3, så ville der ikke være nogen opdatering i toppunktet C.
Den næste kant er (A, D). Da (0 + 5) er lig med 5, så ville der ikke være nogen opdatering i toppunktet D.
Den næste kant er (B, E). Da (1 - 1) er lig med 0, hvilket er mindre end 5, så opdater:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
8 til 1 multiplekser
= 1 - 1 = 0
Den næste kant er (C, E). Da (3 + 3) er lig med 6, hvilket er større end 5, så ville der ikke være nogen opdatering i toppunktet E.
Den næste kant er (D, C). Da (5 - 2) er lig med 3, ville der ikke være nogen opdatering i toppunktet C.
Den næste kant er (D, F). Da (5 - 1) er lig med 4, så ville der ikke være nogen opdatering i toppunktet F.
Den næste kant er (E, F). Da (5 + 3) er lig med 8, hvilket er større end 4, så ville der ikke være nogen opdatering i toppunktet F.
Den næste kant er (C, B). Da (3 - 2) er lig med 1`, så ville der ikke være nogen opdatering i toppunktet B.
Tredje iteration
Vi vil udføre de samme trin, som vi gjorde i de tidligere iterationer. Vi vil observere, at der ikke vil være nogen opdatering i afstanden mellem hjørner.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Tidskompleksitet
Tidskompleksiteten af Bellman ford-algoritmen ville væ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
Derfor er afstanden til toppunkt 3 5.
Overvej kanten (1, 2). Angiv toppunkt '1' som 'u' og toppunkt '2' som 'v'. Brug nu den afslappende formel:
d(u) = 0
d(v) = ∞
10 ml til ounces
c(u, v) = 4
Da (0 + 4) er mindre end ∞, så opdater
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Derfor er afstanden til toppunkt 2 4.
Overvej kanten (3, 2). Angiv toppunkt '3' som 'u' og toppunkt '2' som 'v'. Brug nu den afslappende formel:
d(u) = 5
d(v) = 4
c(u, v) = 7
Da (5 + 7) er større end 4, så ville der ikke være nogen opdatering i toppunktet 2.
Overvej kanten (2, 4). Angiv toppunkt '2' som 'u' og toppunkt '4' som 'v'. Brug nu den afslappende formel:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Da (4 + 7) er lig med 11, hvilket er mindre end ∞, så opdater
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Derfor er afstanden til top 4 11.
Overvej kanten (4, 3). Angiv toppunkt '4' som 'u' og toppunkt '3' som 'v'. Brug nu den afslappende formel:
d(u) = 11
d(v) = 5
c(u, v) = -15
Da (11 - 15) er lig med -4, hvilket er mindre end 5, så opdater
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Derfor er afstanden til toppunkt 3 -4.
Nu går vi til den anden iteration.
Anden iteration
Nu vil vi igen tjekke alle kanterne. Den første kant er (1, 3). Da (0 + 5) er lig med 5, hvilket er større end -4, så ville der ikke være nogen opdatering i toppunktet 3.
Den næste kant er (1, 2). Da (0 + 4) er lig med 4, ville der ikke være nogen opdatering i toppunktet 2.
Den næste kant er (3, 2). Da (-4 + 7) er lig med 3, hvilket er mindre end 4, så opdater:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Derfor er værdien ved toppunkt 2 3.
Den næste kant er (2, 4). Da (3+7) er lig med 10, hvilket er mindre end 11, så opdater
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Derfor er værdien ved toppunkt 4 10.
java-strengen indeholder
Den næste kant er (4, 3). Da (10 - 15) er lig med -5, hvilket er mindre end -4, så opdater:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Derfor er værdien ved toppunkt 3 -5.
Nu går vi til den tredje iteration.
Tredje iteration
Nu vil vi igen tjekke alle kanter. Den første kant er (1, 3). Da (0 + 5) er lig med 5, hvilket er større end -5, så ville der ikke være nogen opdatering i toppunktet 3.
Den næste kant er (1, 2). Da (0 + 4) er lig med 4, hvilket er større end 3, så ville der ikke være nogen opdatering i toppunktet 2.
Den næste kant er (3, 2). Da (-5 + 7) er lig med 2, hvilket er mindre end 3, så opdater:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Derfor er værdien ved toppunkt 2 2.
Den næste kant er (2, 4). Da (2 + 7) er lig med 9, hvilket er mindre end 10, så opdater:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Derfor er værdien ved toppunkt 4 9.
Den næste kant er (4, 3). Da (9 - 15) er lig med -6, hvilket er mindre end -5, så opdater:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Derfor er værdien ved toppunkt 3 -6.
Da grafen indeholder 4 hjørner, så ifølge bellman ford-algoritmen, ville der kun være 3 iterationer. Hvis vi forsøger at udføre 4thiteration på grafen, bør afstanden af toppunkterne fra det givne toppunkt ikke ændre sig. Hvis afstanden varierer, betyder det, at bellman ford-algoritmen ikke giver det rigtige svar.
4thiteration
Den første kant er (1, 3). Da (0 +5) er lig med 5, hvilket er større end -6, så ville der ikke være nogen ændring i toppunktet 3.
Den næste kant er (1, 2). Da (0 + 4) er større end 2, ville der ikke være nogen opdatering.
Den næste kant er (3, 2). Da (-6 + 7) er lig med 1, hvilket er mindre end 3, så opdater:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
I dette tilfælde opdateres toppunktets værdi. Så vi konkluderer, at bellman ford-algoritmen ikke virker, når grafen indeholder den negative vægtcyklus.
Derfor er værdien ved toppunkt 2 1.