Bellman ford-algoritmen er en algoritme for korteste vei med én kilde. Denne algoritmen brukes til å finne den korteste avstanden fra enkelt toppunkt til alle de andre toppunktene i en vektet graf. Det er forskjellige andre algoritmer som brukes for å finne den korteste veien som Dijkstra-algoritmen, osv. Hvis den vektede grafen inneholder de negative vektverdiene, bekrefter ikke Dijkstra-algoritmen om den gir riktig svar eller ikke. I motsetning til Dijkstra-algoritmen, garanterer bellman ford-algoritmen riktig svar selv om den vektede grafen inneholder de negative vektverdiene.
Regelen for denne algoritmen
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Tenk på grafen nedenfor:
Som vi kan observere i grafen ovenfor at noen av vektene er negative. Grafen ovenfor inneholder 6 toppunkter, så vi vil fortsette å slappe av til de 5 toppunktene. Her vil vi slappe av alle kantene 5 ganger. Løkken vil iterere 5 ganger for å få riktig svar. Hvis løkken itereres mer enn 5 ganger, vil også svaret være det samme, det vil si at det ikke vil være noen endring i avstanden mellom toppunktene.
Avslappende betyr:
murer formel
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 avstanden til toppunktet B 6.
Tenk på kanten (A, C). Angi toppunkt 'A' som 'u' og toppunkt 'C' som 'v'. Bruk nå den avslappende formelen:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Siden (0 + 4) er mindre enn ∞, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Derfor er avstanden til toppunktet C 4.
Tenk på kanten (A, D). Angi toppunkt 'A' som 'u' og toppunkt 'D' som 'v'. Bruk nå den avslappende formelen:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Siden (0 + 5) er mindre enn ∞, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Derfor er avstanden til toppunktet D 5.
Tenk på kanten (B, E). Angi toppunkt 'B' som 'u' og toppunkt 'E' som 'v'. Bruk nå den avslappende formelen:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Siden (6 - 1) er mindre enn ∞, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Derfor er avstanden til toppunktet E 5.
Tenk på kanten (C, E). Angi toppunkt 'C' som 'u' og toppunkt 'E' som 'v'. Bruk nå den avslappende formelen:
d(u) = 4
d(v) = 5
c(u, v) = 3
Siden (4 + 3) er større enn 5, vil det ikke være noen oppdatering. Verdien ved toppunktet E er 5.
Tenk på kanten (D, C). Angi toppunkt 'D' som 'u' og toppunkt 'C' som 'v'. Bruk nå den avslappende formelen:
d(u) = 5
d(v) = 4
c(u, v) = -2
Siden (5 -2) er mindre enn 4, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Derfor er avstanden til toppunktet C 3.
Tenk på kanten (D, F). Angi toppunkt 'D' som 'u' og toppunkt 'F' som 'v'. Bruk nå den avslappende formelen:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Siden (5 -1) er mindre enn ∞, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Derfor er avstanden til toppunktet F 4.
Tenk på kanten (E, F). Angi toppunkt 'E' som 'u' og toppunkt 'F' som 'v'. Bruk nå den avslappende formelen:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Siden (5 + 3) er større enn 4, vil det ikke være noen oppdatering av avstandsverdien til toppunktet F.
Tenk på kanten (C, B). Angi toppunkt 'C' som 'u' og toppunkt 'B' som 'v'. Bruk nå den avslappende formelen:
d(u) = 3
d(v) = 6
c(u, v) = -2
Siden (3 - 2) er mindre enn 6, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Derfor er avstanden til toppunktet B 1.
Nå er den første iterasjonen fullført. Vi går til den andre iterasjonen.
Andre iterasjon:
I den andre iterasjonen sjekker vi igjen alle kantene. Den første kanten er (A, B). Siden (0 + 6) er større enn 1, vil det ikke være noen oppdatering i toppunktet B.
Den neste kanten er (A, C). Siden (0 + 4) er større enn 3, vil det ikke være noen oppdatering i toppunktet C.
Den neste kanten er (A, D). Siden (0 + 5) er lik 5, vil det ikke være noen oppdatering i toppunktet D.
Den neste kanten er (B, E). Siden (1 - 1) er lik 0 som er mindre enn 5, så oppdater:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
"hva er forskjellen mellom en løve og en tiger"
= 1 - 1 = 0
Den neste kanten er (C, E). Siden (3 + 3) er lik 6 som er større enn 5, vil det ikke være noen oppdatering i toppunktet E.
Den neste kanten er (D, C). Siden (5 - 2) er lik 3, vil det ikke være noen oppdatering i toppunktet C.
Den neste kanten er (D, F). Siden (5 - 1) er lik 4, vil det ikke være noen oppdatering i toppunktet F.
Den neste kanten er (E, F). Siden (5 + 3) er lik 8 som er større enn 4, vil det ikke være noen oppdatering i toppunktet F.
Den neste kanten er (C, B). Siden (3 - 2) er lik 1` vil det ikke være noen oppdatering i toppunktet B.
Tredje iterasjon
Vi vil utføre de samme trinnene som vi gjorde i de forrige iterasjonene. Vi vil observere at det ikke vil være noen oppdatering i avstanden til hjørnene.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Tidskompleksitet
Tidskompleksiteten til Bellman ford-algoritmen vil 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 avstanden til toppunkt 3 5.
Tenk på kanten (1, 2). Angi toppunkt '1' som 'u' og toppunkt '2' som 'v'. Bruk nå den avslappende formelen:
d(u) = 0
d(v) = ∞
deterministiske endelige automater
c(u, v) = 4
Siden (0 + 4) er mindre enn ∞, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Derfor er avstanden til toppunkt 2 4.
Tenk på kanten (3, 2). Angi toppunkt '3' som 'u' og toppunkt '2' som 'v'. Bruk nå den avslappende formelen:
d(u) = 5
d(v) = 4
c(u, v) = 7
Siden (5 + 7) er større enn 4, vil det ikke være noen oppdatering i toppunktet 2.
Tenk på kanten (2, 4). Angi toppunkt '2' som 'u' og toppunkt '4' som 'v'. Bruk nå den avslappende formelen:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Siden (4 + 7) er lik 11 som er mindre enn ∞, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Derfor er avstanden til toppunkt 4 11.
Tenk på kanten (4, 3). Angi toppunkt '4' som 'u' og toppunkt '3' som 'v'. Bruk nå den avslappende formelen:
d(u) = 11
d(v) = 5
c(u, v) = -15
Siden (11 - 15) er lik -4 som er mindre enn 5, så oppdater
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Derfor er avstanden til toppunkt 3 -4.
Nå går vi til den andre iterasjonen.
Andre iterasjon
Nå skal vi igjen sjekke alle kantene. Den første kanten er (1, 3). Siden (0 + 5) er lik 5 som er større enn -4, vil det ikke være noen oppdatering i toppunktet 3.
Den neste kanten er (1, 2). Siden (0 + 4) er lik 4, vil det ikke være noen oppdatering i toppunktet 2.
Den neste kanten er (3, 2). Siden (-4 + 7) er lik 3 som er mindre enn 4, så oppdater:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Derfor er verdien ved toppunkt 2 3.
Den neste kanten er (2, 4). Siden (3+7) er lik 10 som er mindre enn 11, så oppdater
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Derfor er verdien ved toppunkt 4 10.
forberede seg på test mockito
Den neste kanten er (4, 3). Siden (10 - 15) er lik -5 som er mindre enn -4, så oppdater:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Derfor er verdien ved toppunkt 3 -5.
Nå går vi til den tredje iterasjonen.
Tredje iterasjon
Nå skal vi igjen sjekke alle kantene. Den første kanten er (1, 3). Siden (0 + 5) er lik 5 som er større enn -5, vil det ikke være noen oppdatering i toppunktet 3.
Den neste kanten er (1, 2). Siden (0 + 4) er lik 4 som er større enn 3, vil det ikke være noen oppdatering i toppunktet 2.
Den neste kanten er (3, 2). Siden (-5 + 7) er lik 2 som er mindre enn 3, så oppdater:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Derfor er verdien ved toppunkt 2 2.
Den neste kanten er (2, 4). Siden (2 + 7) er lik 9 som er mindre enn 10, så oppdater:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Derfor er verdien ved toppunkt 4 9.
Den neste kanten er (4, 3). Siden (9 - 15) er lik -6 som er mindre enn -5, så oppdater:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Derfor er verdien ved toppunkt 3 -6.
Siden grafen inneholder 4 hjørner, så ifølge bellman ford-algoritmen, ville det bare være 3 iterasjoner. Hvis vi prøver å utføre 4thiterasjon på grafen, bør avstanden til toppunktene fra det gitte toppunktet ikke endres. Hvis avstanden varierer, betyr det at bellman ford-algoritmen ikke gir det riktige svaret.
4thiterasjon
Den første kanten er (1, 3). Siden (0 +5) er lik 5 som er større enn -6, vil det ikke være noen endring i toppunktet 3.
Den neste kanten er (1, 2). Siden (0 + 4) er større enn 2, vil det ikke være noen oppdatering.
Den neste kanten er (3, 2). Siden (-6 + 7) er lik 1 som er mindre enn 3, så oppdater:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
I dette tilfellet oppdateres verdien av toppunktet. Så vi konkluderer med at bellman ford-algoritmen ikke fungerer når grafen inneholder den negative vektsyklusen.
Derfor er verdien ved toppunkt 2 1.