Algoritmus Bellman ford je jednozdrojový algoritmus najkratšej cesty. Tento algoritmus sa používa na nájdenie najkratšej vzdialenosti od jedného vrcholu ku všetkým ostatným vrcholom váženého grafu. Na nájdenie najkratšej cesty sa používajú rôzne iné algoritmy, ako je Dijkstrov algoritmus atď. Ak vážený graf obsahuje záporné hodnoty váh, potom Dijkstrov algoritmus nepotvrdzuje, či dáva správnu odpoveď alebo nie. Algoritmus Bellman ford na rozdiel od Dijkstrovho algoritmu zaručuje správnu odpoveď, aj keď vážený graf obsahuje záporné hodnoty váh.
Pravidlo tohto algoritmu
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Zvážte nasledujúci graf:
Ako môžeme vidieť na vyššie uvedenom grafe, niektoré váhy sú záporné. Vyššie uvedený graf obsahuje 6 vrcholov, takže budeme pokračovať v relaxácii až do 5 vrcholov. Tu uvoľníme všetky okraje 5-krát. Slučka sa zopakuje 5-krát, aby ste dostali správnu odpoveď. Ak sa slučka opakuje viac ako 5-krát, aj odpoveď bude rovnaká, t.j. vzdialenosť medzi vrcholmi by sa nezmenila.
Relaxačný znamená:
synchronizácia vlákien
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
Preto je vzdialenosť vrcholu B 6.
Zvážte okraj (A, C). Označte vrchol „A“ ako „u“ a vrchol „C“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Keďže (0 + 4) je menšie ako ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Preto je vzdialenosť vrcholu C 4.
Zvážte okraj (A, D). Označte vrchol „A“ ako „u“ a vrchol „D“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Keďže (0 + 5) je menšie ako ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Preto je vzdialenosť vrcholu D 5.
Zvážte okraj (B, E). Označte vrchol „B“ ako „u“ a vrchol „E“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Keďže (6 - 1) je menej ako ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Preto je vzdialenosť vrcholu E 5.
Zvážte okraj (C, E). Označte vrchol „C“ ako „u“ a vrchol „E“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 4
d(v) = 5
c(u, v) = 3
Keďže (4 + 3) je väčšie ako 5, nedôjde k žiadnej aktualizácii. Hodnota vo vrchole E je 5.
Zvážte okraj (D, C). Označte vrchol „D“ ako „u“ a vrchol „C“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 5
d(v) = 4
c(u, v) = -2
Keďže (5 -2) je menej ako 4, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Preto je vzdialenosť vrcholu C 3.
Zvážte hranu (D, F). Označte vrchol „D“ ako „u“ a vrchol „F“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 5
d(v) = ∞
čo znamená xdxd
c(u, v) = -1
Keďže (5 -1) je menej ako ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Preto je vzdialenosť vrcholu F 4.
Zvážte okraj (E, F). Označte vrchol „E“ ako „u“ a vrchol „F“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Keďže (5 + 3) je väčšie ako 4, nedochádzalo by k žiadnej aktualizácii hodnoty vzdialenosti vrcholu F.
Zvážte okraj (C, B). Označte vrchol „C“ ako „u“ a vrchol „B“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 3
d(v) = 6
c(u, v) = -2
Keďže (3 - 2) je menej ako 6, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Preto je vzdialenosť vrcholu B 1.
Teraz je prvá iterácia dokončená. Prejdeme k druhej iterácii.
Druhá iterácia:
V druhej iterácii opäť skontrolujeme všetky hrany. Prvá hrana je (A, B). Keďže (0 + 6) je väčšie ako 1, nedôjde k žiadnej aktualizácii vo vrchole B.
Ďalšia hrana je (A, C). Keďže (0 + 4) je väčšie ako 3, vo vrchole C by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (A, D). Keďže (0 + 5) sa rovná 5, vo vrchole D by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (B, E). Keďže (1 - 1) sa rovná 0, čo je menej ako 5, aktualizujte:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
= 1 - 1 = 0
Ďalšia hrana je (C, E). Keďže (3 + 3) sa rovná 6, čo je väčšie ako 5, vo vrchole E by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (D, C). Keďže (5 - 2) sa rovná 3, vo vrchole C by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (D, F). Keďže (5 - 1) sa rovná 4, vo vrchole F by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (E, F). Keďže (5 + 3) sa rovná 8, čo je väčšie ako 4, takže vo vrchole F nebude žiadna aktualizácia.
Ďalšia hrana je (C, B). Keďže (3 - 2) sa rovná 1`, vo vrchole B by nedošlo k žiadnej aktualizácii.
Tretia iterácia
Vykonáme rovnaké kroky ako v predchádzajúcich iteráciách. Pozorujeme, že nedôjde k žiadnej aktualizácii vzdialenosti vrcholov.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Časová zložitosť
Časová zložitosť Bellmanovho fordovho algoritmu by bola 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
Preto je vzdialenosť vrcholu 3 5.
Zvážte okraj (1, 2). Označte vrchol „1“ ako „u“ a vrchol „2“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Keďže (0 + 4) je menšie ako ∞, aktualizujte
reakčná mapa
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Preto je vzdialenosť vrcholu 2 4.
Zvážte okraj (3, 2). Označte vrchol „3“ ako „u“ a vrchol „2“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 5
d(v) = 4
c(u, v) = 7
Keďže (5 + 7) je väčšie ako 4, vo vrchole 2 by nedošlo k žiadnej aktualizácii.
Zvážte okraj (2, 4). Označte vrchol „2“ ako „u“ a vrchol „4“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Keďže (4 + 7) sa rovná 11, čo je menej ako ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Preto je vzdialenosť vrcholu 4 11.
Zvážte okraj (4, 3). Označte vrchol „4“ ako „u“ a vrchol „3“ ako „v“. Teraz použite relaxačný vzorec:
d(u) = 11
d(v) = 5
c(u, v) = -15
Keďže (11 - 15) sa rovná -4, čo je menej ako 5, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 11-15 = -4
Preto je vzdialenosť vrcholu 3 -4.
Teraz prejdeme k druhej iterácii.
Druhá iterácia
Teraz znova skontrolujeme všetky okraje. Prvá hrana je (1, 3). Keďže (0 + 5) sa rovná 5, čo je väčšie ako -4, vo vrchole 3 by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (1, 2). Keďže (0 + 4) sa rovná 4, vo vrchole 2 by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (3, 2). Keďže (-4 + 7) sa rovná 3, čo je menej ako 4, aktualizujte:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Preto je hodnota vo vrchole 2 3.
Ďalšia hrana je (2, 4). Keďže ( 3+7) sa rovná 10, čo je menej ako 11, aktualizujte
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Preto je hodnota vo vrchole 4 10.
Greatandhra
Ďalšia hrana je (4, 3). Keďže (10 - 15) sa rovná -5, čo je menej ako -4, aktualizujte:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Preto je hodnota vo vrchole 3 -5.
Teraz prejdeme k tretej iterácii.
Tretia iterácia
Teraz opäť skontrolujeme všetky okraje. Prvá hrana je (1, 3). Keďže (0 + 5) sa rovná 5, čo je väčšie ako -5, vo vrchole 3 by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (1, 2). Keďže (0 + 4) sa rovná 4, čo je väčšie ako 3, vo vrchole 2 by nedošlo k žiadnej aktualizácii.
Ďalšia hrana je (3, 2). Keďže (-5 + 7) sa rovná 2, čo je menej ako 3, aktualizujte:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Preto je hodnota vo vrchole 2 2.
Ďalšia hrana je (2, 4). Keďže (2 + 7) sa rovná 9, čo je menej ako 10, aktualizujte:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Preto je hodnota vo vrchole 4 9.
Ďalšia hrana je (4, 3). Keďže (9 - 15) sa rovná -6, čo je menej ako -5, aktualizujte:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Preto je hodnota vo vrchole 3 -6.
Keďže graf obsahuje 4 vrcholy, tak podľa bellman fordovho algoritmu by boli len 3 iterácie. Ak sa pokúsime vykonať 4thiterácii na grafe by sa vzdialenosť vrcholov od daného vrcholu nemala meniť. Ak sa vzdialenosť mení, znamená to, že algoritmus Bellman ford neposkytuje správnu odpoveď.
4thiterácia
Prvá hrana je (1, 3). Keďže (0 +5) sa rovná 5, čo je väčšie ako -6, vo vrchole 3 by nenastala žiadna zmena.
Ďalšia hrana je (1, 2). Keďže (0 + 4) je väčšie ako 2, nedôjde k žiadnej aktualizácii.
Ďalšia hrana je (3, 2). Keďže (-6 + 7) sa rovná 1, čo je menej ako 3, aktualizujte:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
V tomto prípade sa aktualizuje hodnota vrcholu. Takže sme dospeli k záveru, že bellman ford algoritmus nefunguje, keď graf obsahuje negatívny váhový cyklus.
Preto je hodnota vo vrchole 2 1.