L'algoritme Bellman Ford és un algorisme del camí més curt d'una sola font. Aquest algorisme s'utilitza per trobar la distància més curta des d'un únic vèrtex fins a tots els altres vèrtexs d'un gràfic ponderat. Hi ha diversos altres algorismes que s'utilitzen per trobar el camí més curt com l'algorisme de Dijkstra, etc. Si el gràfic ponderat conté els valors de pes negatius, aleshores l'algoritme de Dijkstra no confirma si produeix la resposta correcta o no. A diferència de l'algorisme de Dijkstra, l'algoritme de Bellman Ford garanteix la resposta correcta fins i tot si el gràfic ponderat conté els valors de pes negatius.
Regla d'aquest algorisme
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Considereu el gràfic següent:
Com podem observar en el gràfic anterior, alguns dels pesos són negatius. El gràfic anterior conté 6 vèrtexs, així que anirem relaxant-nos fins als 5 vèrtexs. Aquí, relaxarem totes les vores 5 vegades. El bucle repetirà 5 vegades per obtenir la resposta correcta. Si el bucle es repeteix més de 5 vegades, també la resposta serà la mateixa, és a dir, no hi hauria cap canvi en la distància entre els vèrtexs.
Relaxar-se significa:
prime no code in java
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
Per tant, la distància del vèrtex B és 6.
Considereu l'aresta (A, C). Denoteu el vèrtex 'A' com a 'u' i el vèrtex 'C' com a 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Com que (0 + 4) és menor que ∞, actualitzeu
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Per tant, la distància del vèrtex C és 4.
Considereu la vora (A, D). Denoteu el vèrtex 'A' com a 'u' i el vèrtex 'D' com a 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Com que (0 + 5) és menor que ∞, actualitzeu
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Per tant, la distància del vèrtex D és 5.
Considereu la vora (B, E). Denoteu el vèrtex 'B' com 'u' i el vèrtex 'E' com 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Com que (6 - 1) és menor que ∞, per tant, actualitzeu
d(v) = d(u) + c(u , v)
d(v) = 6 - 1= 5
Per tant, la distància del vèrtex E és 5.
Considereu l'aresta (C, E). Denoteu el vèrtex 'C' com 'u' i el vèrtex 'E' com 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 4
d(v) = 5
c(u, v) = 3
Com que (4 + 3) és més gran que 5, no hi haurà actualització. El valor al vèrtex E és 5.
Considereu l'aresta (D, C). Denoteu el vèrtex 'D' com 'u' i el vèrtex 'C' com 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 5
d(v) = 4
c(u, v) = -2
Com que (5 -2) és inferior a 4, actualitzeu-lo
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Per tant, la distància del vèrtex C és 3.
Considereu l'aresta (D, F). Denoteu el vèrtex 'D' com 'u' i el vèrtex 'F' com 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Com que (5 -1) és menor que ∞, per tant, actualitzeu
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Per tant, la distància del vèrtex F és 4.
Considereu l'aresta (E, F). Denoteu el vèrtex 'E' com 'u' i el vèrtex 'F' com 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Com que (5 + 3) és més gran que 4, no hi hauria cap actualització sobre el valor de distància del vèrtex F.
Considereu l'aresta (C, B). Denoteu el vèrtex 'C' com 'u' i el vèrtex 'B' com 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 3
d(v) = 6
c(u, v) = -2
Com que (3 - 2) és inferior a 6, actualitzeu-lo
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Per tant, la distància del vèrtex B és 1.
Ara s'ha completat la primera iteració. Passem a la segona iteració.
Segona iteració:
A la segona iteració, tornem a comprovar totes les vores. La primera vora és (A, B). Com que (0 + 6) és més gran que 1, no hi hauria cap actualització al vèrtex B.
La vora següent és (A, C). Com que (0 + 4) és més gran que 3, no hi hauria actualització al vèrtex C.
La vora següent és (A, D). Com que (0 + 5) és igual a 5, no hi hauria cap actualització al vèrtex D.
La vora següent és (B, E). Com que (1 - 1) és igual a 0, que és inferior a 5, així que actualitzeu:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
La vora següent és (C, E). Com que (3 + 3) és igual a 6, que és més gran que 5, no hi hauria cap actualització al vèrtex E.
La vora següent és (D, C). Com que (5 - 2) és igual a 3, no hi hauria cap actualització al vèrtex C.
La vora següent és (D, F). Com que (5 - 1) és igual a 4, no hi hauria cap actualització al vèrtex F.
mergesort java
La vora següent és (E, F). Com que (5 + 3) és igual a 8, que és més gran que 4, no hi hauria cap actualització al vèrtex F.
La vora següent és (C, B). Com que (3 - 2) és igual a 1`, no hi hauria cap actualització al vèrtex B.
Tercera iteració
Farem els mateixos passos que vam fer a les iteracions anteriors. Observarem que no hi haurà actualització en la distància de vèrtexs.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Complexitat temporal
La complexitat temporal de l'algorisme de Bellman ford seria 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
Per tant, la distància del vèrtex 3 és 5.
Considereu la vora (1, 2). Denoteu el vèrtex '1' com a 'u' i el vèrtex '2' com a 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Com que (0 + 4) és menor que ∞, actualitzeu
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Per tant, la distància del vèrtex 2 és 4.
Considereu la vora (3, 2). Denoteu el vèrtex '3' com a 'u' i el vèrtex '2' com a 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 5
màquina virtual java
d(v) = 4
c(u, v) = 7
Com que (5 + 7) és més gran que 4, no hi hauria cap actualització al vèrtex 2.
Considereu la vora (2, 4). Denoteu el vèrtex '2' com a 'u' i el vèrtex '4' com a 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Com que (4 + 7) és igual a 11, que és menor que ∞, per tant actualitzeu
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Per tant, la distància del vèrtex 4 és 11.
Considereu la vora (4, 3). Denoteu el vèrtex '4' com a 'u' i el vèrtex '3' com a 'v'. Ara utilitzeu la fórmula relaxant:
d(u) = 11
d(v) = 5
c(u , v) = -15
Com que (11 - 15) és igual a -4, que és inferior a 5, actualitzeu-lo
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Per tant, la distància del vèrtex 3 és -4.
Ara passem a la segona iteració.
Segona iteració
Ara, de nou, comprovarem totes les vores. La primera vora és (1, 3). Com que (0 + 5) és igual a 5, que és més gran que -4, no hi hauria cap actualització al vèrtex 3.
La vora següent és (1, 2). Com que (0 + 4) és igual a 4, no hi hauria cap actualització al vèrtex 2.
La vora següent és (3, 2). Com que (-4 + 7) és igual a 3, que és inferior a 4, actualitzeu:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Per tant, el valor al vèrtex 2 és 3.
La vora següent és (2, 4). Com que (3+7) és igual a 10, que és menor que 11, actualitzeu
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Per tant, el valor al vèrtex 4 és 10.
bucle infinit
La vora següent és (4, 3). Com que (10 - 15) és igual a -5, que és menor que -4, actualitzeu:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Per tant, el valor al vèrtex 3 és -5.
Ara passem a la tercera iteració.
Tercera iteració
Ara tornarem a comprovar totes les vores. La primera vora és (1, 3). Com que (0 + 5) és igual a 5, que és més gran que -5, no hi hauria cap actualització al vèrtex 3.
La vora següent és (1, 2). Com que (0 + 4) és igual a 4, que és més gran que 3, no hi hauria cap actualització al vèrtex 2.
La vora següent és (3, 2). Com que (-5 + 7) és igual a 2, que és menor que 3, actualitzeu:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Per tant, el valor al vèrtex 2 és 2.
La vora següent és (2, 4). Com que (2 + 7) és igual a 9, que és menor que 10, actualitzeu:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Per tant, el valor al vèrtex 4 és 9.
La vora següent és (4, 3). Com que (9 - 15) és igual a -6, que és inferior a -5, així que actualitzeu:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Per tant, el valor al vèrtex 3 és -6.
Com que el gràfic conté 4 vèrtexs, segons l'algorisme de Bellman Ford, només hi hauria 3 iteracions. Si intentem realitzar 4thiteració al gràfic, la distància dels vèrtexs del vèrtex donat no hauria de canviar. Si la distància varia, vol dir que l'algoritme de Bellman Ford no proporciona la resposta correcta.
4thiteració
La primera vora és (1, 3). Com que (0 + 5) és igual a 5, que és més gran que -6, no hi hauria cap canvi en el vèrtex 3.
La vora següent és (1, 2). Com que (0 + 4) és més gran que 2, no hi hauria actualització.
La vora següent és (3, 2). Com que (-6 + 7) és igual a 1, que és inferior a 3, actualitzeu:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
En aquest cas, el valor del vèrtex s'actualitza. Per tant, concloem que l'algorisme de Bellman Ford no funciona quan el gràfic conté el cicle de pes negatiu.
Per tant, el valor al vèrtex 2 és 1.