Algoritmul Bellman Ford este un algoritm cu cea mai scurtă cale cu o singură sursă. Acest algoritm este folosit pentru a găsi cea mai scurtă distanță de la un singur vârf la toate celelalte vârfuri ale unui grafic ponderat. Există diverși alți algoritmi folosiți pentru a găsi calea cea mai scurtă, cum ar fi algoritmul Dijkstra, etc. Dacă graficul ponderat conține valori negative ale greutății, atunci algoritmul Dijkstra nu confirmă dacă produce răspunsul corect sau nu. Spre deosebire de algoritmul Dijkstra, algoritmul Bellman Ford garantează răspunsul corect chiar dacă graficul ponderat conține valori negative ale greutății.
Regula acestui algoritm
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Luați în considerare graficul de mai jos:
După cum putem observa în graficul de mai sus, unele dintre ponderi sunt negative. Graficul de mai sus conține 6 vârfuri, așa că ne vom relaxa până la cele 5 vârfuri. Aici, vom relaxa toate marginile de 5 ori. Bucla se va repeta de 5 ori pentru a obține răspunsul corect. Dacă bucla este repetată de mai mult de 5 ori, atunci și răspunsul va fi același, adică nu ar exista nicio modificare a distanței dintre vârfuri.
Relaxare înseamnă:
variabile nginx
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
Prin urmare, distanța vârfului B este 6.
Luați în considerare muchia (A, C). Notați vârful „A” ca „u” și vârful „C” ca „v”. Acum folosește formula relaxantă:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Deoarece (0 + 4) este mai mic decât ∞, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Prin urmare, distanța vârfului C este 4.
Luați în considerare muchia (A, D). Notați vârful „A” ca „u” și vârful „D” ca „v”. Acum folosește formula relaxantă:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Deoarece (0 + 5) este mai mic decât ∞, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Prin urmare, distanța vârfului D este 5.
Luați în considerare marginea (B, E). Notați vârful „B” ca „u” și vârful „E” ca „v”. Acum folosește formula relaxantă:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Deoarece (6 - 1) este mai mic decât ∞, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 6 - 1= 5
Prin urmare, distanța vârfului E este 5.
Luați în considerare marginea (C, E). Notați vârful „C” ca „u” și vârful „E” ca „v”. Acum folosește formula relaxantă:
d(u) = 4
d(v) = 5
c(u, v) = 3
Deoarece (4 + 3) este mai mare decât 5, deci nu va exista nicio actualizare. Valoarea la vârful E este 5.
Luați în considerare muchia (D, C). Notați vârful „D” ca „u” și vârful „C” ca „v”. Acum folosește formula relaxantă:
d(u) = 5
d(v) = 4
c(u, v) = -2
Deoarece (5 -2) este mai mic de 4, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Prin urmare, distanța vârfului C este 3.
Luați în considerare muchia (D, F). Notați vârful „D” ca „u” și vârful „F” ca „v”. Acum folosește formula relaxantă:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Deoarece (5 -1) este mai mic decât ∞, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Prin urmare, distanța vârfului F este 4.
Luați în considerare marginea (E, F). Notați vârful „E” ca „u” și vârful „F” ca „v”. Acum folosește formula relaxantă:
d(u) = 5
d(v) = ∞
c(u, v) = 3
tutorial java jfx
Deoarece (5 + 3) este mai mare decât 4, deci nu ar exista nicio actualizare asupra valorii distanței a vârfului F.
Luați în considerare marginea (C, B). Notați vârful „C” ca „u” și vârful „B” ca „v”. Acum folosește formula relaxantă:
d(u) = 3
d(v) = 6
c(u, v) = -2
Deoarece (3 - 2) este mai mic de 6, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Prin urmare, distanța vârfului B este 1.
Acum prima iterație este finalizată. Trecem la a doua iterație.
A doua iterație:
În a doua iterație, verificăm din nou toate marginile. Prima muchie este (A, B). Deoarece (0 + 6) este mai mare decât 1, nu ar exista nicio actualizare în vârful B.
Următoarea muchie este (A, C). Deoarece (0 + 4) este mai mare decât 3, nu ar exista nicio actualizare în vârful C.
Următoarea muchie este (A, D). Deoarece (0 + 5) este egal cu 5, nu ar exista nicio actualizare în vârful D.
Următoarea muchie este (B, E). Deoarece (1 - 1) este egal cu 0, care este mai mic de 5, deci actualizați:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
Următoarea muchie este (C, E). Deoarece (3 + 3) este egal cu 6, care este mai mare decât 5, nu ar exista nicio actualizare în vârful E.
Următoarea muchie este (D, C). Deoarece (5 - 2) este egal cu 3, deci nu ar exista nicio actualizare în vârful C.
Următoarea muchie este (D, F). Deoarece (5 - 1) este egal cu 4, nu ar exista nicio actualizare în vârful F.
Următoarea muchie este (E, F). Deoarece (5 + 3) este egal cu 8, care este mai mare decât 4, nu ar exista nicio actualizare în vârful F.
Următoarea muchie este (C, B). Deoarece (3 - 2) este egal cu 1`, nu ar exista nicio actualizare în vârful B.
A treia iterație
Vom efectua aceiași pași ca și în iterațiile anterioare. Vom observa că nu va exista nicio actualizare în distanța vârfurilor.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Complexitatea timpului
Complexitatea temporală a algoritmului Bellman ford ar fi O(E|V| - 1).
straturi model osi
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
Prin urmare, distanța vârfului 3 este 5.
Luați în considerare marginea (1, 2). Notați vârful „1” ca „u” și vârful „2” ca „v”. Acum folosește formula relaxantă:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Deoarece (0 + 4) este mai mic decât ∞, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Prin urmare, distanța vârfului 2 este 4.
Luați în considerare marginea (3, 2). Notați vârful „3” ca „u” și vârful „2” ca „v”. Acum folosește formula relaxantă:
d(u) = 5
d(v) = 4
c(u, v) = 7
Deoarece (5 + 7) este mai mare decât 4, deci nu ar exista nicio actualizare în vârful 2.
Luați în considerare marginea (2, 4). Notați vârful „2” ca „u” și vârful „4” ca „v”. Acum folosește formula relaxantă:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Deoarece (4 + 7) este egal cu 11 care este mai mic decât ∞, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Prin urmare, distanța vârfului 4 este 11.
Luați în considerare marginea (4, 3). Notați vârful „4” ca „u” și vârful „3” ca „v”. Acum folosește formula relaxantă:
d(u) = 11
d(v) = 5
c(u, v) = -15
Deoarece (11 - 15) este egal cu -4, care este mai mic de 5, deci actualizați
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Prin urmare, distanța vârfului 3 este -4.
Acum trecem la a doua iterație.
A doua iterație
Acum, din nou, vom verifica toate marginile. Prima muchie este (1, 3). Deoarece (0 + 5) este egal cu 5 care este mai mare decât -4, deci nu ar exista nicio actualizare în vârful 3.
Următoarea muchie este (1, 2). Deoarece (0 + 4) este egal cu 4, nu ar exista nicio actualizare în vârful 2.
Următoarea muchie este (3, 2). Deoarece (-4 + 7) este egal cu 3, care este mai mic decât 4, deci actualizați:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Prin urmare, valoarea la vârful 2 este 3.
Următoarea muchie este (2, 4). Deoarece ( 3+7) este egal cu 10, care este mai mic de 11, deci actualizați
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Prin urmare, valoarea la vârful 4 este 10.
hartă java
Următoarea muchie este (4, 3). Deoarece (10 - 15) este egal cu -5, care este mai mic de -4, deci actualizați:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Prin urmare, valoarea la vârful 3 este -5.
Acum trecem la a treia iterație.
A treia iterație
Acum vom verifica din nou toate marginile. Prima muchie este (1, 3). Deoarece (0 + 5) este egal cu 5, care este mai mare decât -5, nu ar exista nicio actualizare în vârful 3.
Următoarea muchie este (1, 2). Deoarece (0 + 4) este egal cu 4, care este mai mare decât 3, nu ar exista nicio actualizare în vârful 2.
Următoarea muchie este (3, 2). Deoarece (-5 + 7) este egal cu 2, care este mai mic de 3, deci actualizați:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Prin urmare, valoarea la vârful 2 este 2.
Următoarea muchie este (2, 4). Deoarece (2 + 7) este egal cu 9, care este mai mic de 10, deci actualizați:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Prin urmare, valoarea la vârful 4 este 9.
Următoarea muchie este (4, 3). Deoarece (9 - 15) este egal cu -6, care este mai mic de -5, deci actualizați:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Prin urmare, valoarea la vârful 3 este -6.
Deoarece graficul conține 4 vârfuri, deci conform algoritmului Bellman Ford, ar exista doar 3 iterații. Dacă încercăm să executăm 4thiterație pe grafic, distanța vârfurilor de la vârful dat nu ar trebui să se schimbe. Dacă distanța variază, înseamnă că algoritmul Bellman Ford nu oferă răspunsul corect.
4threpetare
Prima muchie este (1, 3). Deoarece (0 +5) este egal cu 5, care este mai mare decât -6, nu ar exista nicio modificare în vârful 3.
Următoarea muchie este (1, 2). Deoarece (0 + 4) este mai mare decât 2, nu ar exista nicio actualizare.
Următoarea muchie este (3, 2). Deoarece (-6 + 7) este egal cu 1, care este mai mic de 3, deci actualizați:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
În acest caz, valoarea vârfului este actualizată. Deci, concluzionăm că algoritmul Bellman Ford nu funcționează atunci când graficul conține ciclul de greutate negativă.
Prin urmare, valoarea la vârful 2 este 1.