Algoritmus Bellman ford je algoritmus s nejkratší cestou z jediného zdroje. Tento algoritmus se používá k nalezení nejkratší vzdálenosti od jednoho vrcholu ke všem ostatním vrcholům váženého grafu. K nalezení nejkratší cesty se používají různé další algoritmy, jako je Dijkstrův algoritmus atd. Pokud vážený graf obsahuje záporné hodnoty vah, pak Dijkstrův algoritmus nepotvrzuje, zda dává správnou odpověď nebo ne. Algoritmus Bellman ford na rozdíl od Dijkstrova algoritmu zaručuje správnou odpověď, i když vážený graf obsahuje záporné hodnoty vah.
Pravidlo tohoto algoritmu
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Zvažte níže uvedený graf:
Jak můžeme vidět na výše uvedeném grafu, některé váhy jsou záporné. Výše uvedený graf obsahuje 6 vrcholů, takže budeme pokračovat v relaxaci až do 5 vrcholů. Zde 5x povolíme všechny okraje. Smyčka se bude opakovat 5krát, aby se získala správná odpověď. Pokud je smyčka iterována více než 5krát, bude také odpověď stejná, tj. nedojde k žádné změně vzdálenosti mezi vrcholy.
Relaxační znamená:
java datum nyní
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
Proto je vzdálenost vrcholu B 6.
Zvažte hranu (A, C). Označte vrchol 'A' jako 'u' a vrchol 'C' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Protože (0 + 4) je menší než ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Proto je vzdálenost vrcholu C 4.
Zvažte hranu (A, D). Označte vrchol 'A' jako 'u' a vrchol 'D' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Protože (0 + 5) je menší než ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Vzdálenost vrcholu D je tedy 5.
Zvažte hranu (B, E). Označte vrchol 'B' jako 'u' a vrchol 'E' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Protože (6 - 1) je menší než ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Proto je vzdálenost vrcholu E 5.
Zvažte hranu (C, E). Označte vrchol 'C' jako 'u' a vrchol 'E' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 4
d(v) = 5
c(u, v) = 3
Protože (4 + 3) je větší než 5, nebude žádná aktualizace. Hodnota ve vrcholu E je 5.
Zvažte hranu (D, C). Označte vrchol 'D' jako 'u' a vrchol 'C' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 5
d(v) = 4
c(u, v) = -2
Protože (5 -2) je menší než 4, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Vzdálenost vrcholu C je tedy 3.
Zvažte hranu (D, F). Označte vrchol 'D' jako 'u' a vrchol 'F' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Protože (5 -1) je menší než ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Proto je vzdálenost vrcholu F 4.
Zvažte hranu (E, F). Označte vrchol 'E' jako 'u' a vrchol 'F' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Protože (5 + 3) je větší než 4, nedocházelo by k žádné aktualizaci hodnoty vzdálenosti vrcholu F.
Zvažte hranu (C, B). Označte vrchol 'C' jako 'u' a vrchol 'B' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 3
d(v) = 6
c(u, v) = -2
Protože (3 - 2) je méně než 6, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Vzdálenost vrcholu B je tedy 1.
Nyní je první iterace dokončena. Přejdeme k druhé iteraci.
Druhá iterace:
Ve druhé iteraci opět zkontrolujeme všechny hrany. První hrana je (A, B). Protože (0 + 6) je větší než 1, nedocházelo by k žádné aktualizaci ve vrcholu B.
Další hrana je (A, C). Protože (0 + 4) je větší než 3, nedocházelo by k žádné aktualizaci ve vrcholu C.
Další hrana je (A, D). Protože (0 + 5) se rovná 5, nedocházelo by k žádné aktualizaci ve vrcholu D.
Další hrana je (B, E). Protože (1 - 1) se rovná 0, což je menší než 5, aktualizujte:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
gimp uložit jako jpeg
= 1 - 1 = 0
Další hrana je (C, E). Protože (3 + 3) se rovná 6, což je větší než 5, nedocházelo by k žádné aktualizaci ve vrcholu E.
Další hrana je (D, C). Protože (5 - 2) se rovná 3, nedocházelo by k žádné aktualizaci ve vrcholu C.
Další hrana je (D, F). Protože (5 - 1) se rovná 4, nedocházelo by k žádné aktualizaci ve vrcholu F.
Další hrana je (E, F). Protože (5 + 3) se rovná 8, což je větší než 4, takže ve vrcholu F nedojde k žádné aktualizaci.
Další hrana je (C, B). Protože (3 - 2) se rovná 1`, ve vrcholu B nedojde k žádné aktualizaci.
Třetí iterace
Provedeme stejné kroky jako v předchozích iteracích. Pozorujeme, že nedojde k žádné aktualizaci vzdálenosti vrcholů.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Časová složitost
Časová složitost Bellmanova fordova algoritmu by byla 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
Proto je vzdálenost vrcholu 3 5.
Zvažte hranu (1, 2). Označte vrchol „1“ jako „u“ a vrchol „2“ jako „v“. Nyní použijte relaxační vzorec:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Protože (0 + 4) je menší než ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Proto je vzdálenost vrcholu 2 4.
Zvažte hranu (3, 2). Označte vrchol '3' jako 'u' a vrchol '2' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 5
d(v) = 4
c(u, v) = 7
Protože (5 + 7) je větší než 4, nedocházelo by k žádné aktualizaci ve vrcholu 2.
Zvažte hranu (2, 4). Označte vrchol '2' jako 'u' a vrchol '4' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Protože (4 + 7) se rovná 11, což je méně než ∞, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Proto je vzdálenost vrcholu 4 11.
Zvažte hranu (4, 3). Označte vrchol '4' jako 'u' a vrchol '3' jako 'v'. Nyní použijte relaxační vzorec:
d(u) = 11
d(v) = 5
panda pivot
c(u, v) = -15
Protože (11 - 15) se rovná -4, což je méně než 5, aktualizujte
d(v) = d(u) + c(u , v)
d(v) = 11-15 = -4
Proto je vzdálenost vrcholu 3 -4.
Nyní přejdeme k druhé iteraci.
Druhá iterace
Nyní znovu zkontrolujeme všechny okraje. První hrana je (1, 3). Protože (0 + 5) se rovná 5, což je větší než -4, ve vrcholu 3 by nebyla žádná aktualizace.
Další hrana je (1, 2). Protože (0 + 4) se rovná 4, ve vrcholu 2 by nedocházelo k žádné aktualizaci.
Další hrana je (3, 2). Protože (-4 + 7) se rovná 3, což je méně než 4, aktualizujte:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Proto je hodnota ve vrcholu 2 3.
Další hrana je (2, 4). Protože ( 3+7) se rovná 10, což je méně než 11, aktualizujte
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Proto je hodnota ve vrcholu 4 10.
nekonečná smyčka
Další hrana je (4, 3). Protože (10 - 15) se rovná -5, což je méně než -4, aktualizujte:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Proto je hodnota ve vrcholu 3 -5.
Nyní přejdeme ke třetí iteraci.
Třetí iterace
Nyní znovu zkontrolujeme všechny okraje. První hrana je (1, 3). Protože (0 + 5) se rovná 5, což je větší než -5, ve vrcholu 3 by nedocházelo k žádné aktualizaci.
Další hrana je (1, 2). Protože (0 + 4) se rovná 4, což je větší než 3, ve vrcholu 2 by nedocházelo k žádné aktualizaci.
Další hrana je (3, 2). Protože (-5 + 7) se rovná 2, což je méně než 3, aktualizujte:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Proto je hodnota ve vrcholu 2 2.
Další hrana je (2, 4). Protože (2 + 7) se rovná 9, což je méně než 10, aktualizujte:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Proto je hodnota ve vrcholu 4 9.
Další hrana je (4, 3). Protože (9 - 15) se rovná -6, což je méně než -5, aktualizujte:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Proto je hodnota ve vrcholu 3 -6.
Vzhledem k tomu, že graf obsahuje 4 vrcholy, tak by podle bellmanova fordova algoritmu byly pouze 3 iterace. Pokud se pokusíme provést 4čtiteraci na grafu by se vzdálenost vrcholů od daného vrcholu neměla měnit. Pokud se vzdálenost mění, znamená to, že algoritmus Bellman ford neposkytuje správnou odpověď.
4čtopakování
První hrana je (1, 3). Protože (0 +5) se rovná 5, což je větší než -6, nedojde k žádné změně ve vrcholu 3.
Další hrana je (1, 2). Protože (0 + 4) je větší než 2, nebude žádná aktualizace.
Další hrana je (3, 2). Protože (-6 + 7) se rovná 1, což je méně než 3, aktualizujte:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
V tomto případě se aktualizuje hodnota vrcholu. Došli jsme tedy k závěru, že bellmanův fordův algoritmus nefunguje, když graf obsahuje záporný váhový cyklus.
Proto je hodnota ve vrcholu 2 1.