Algorytm Bellmana Forda to algorytm najkrótszej ścieżki z jednego źródła. Algorytm ten służy do znalezienia najkrótszej odległości od pojedynczego wierzchołka do wszystkich pozostałych wierzchołków grafu ważonego. Istnieje wiele innych algorytmów używanych do znalezienia najkrótszej ścieżki, takich jak algorytm Dijkstry itp. Jeśli wykres ważony zawiera ujemne wartości wag, algorytm Dijkstry nie sprawdza, czy daje poprawną odpowiedź, czy nie. W przeciwieństwie do algorytmu Dijkstry, algorytm Bellmana Forda gwarantuje poprawną odpowiedź nawet jeśli wykres ważony zawiera ujemne wartości wag.
Reguła tego algorytmu
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Rozważ poniższy wykres:
Jak widać na powyższym wykresie, część wag jest ujemna. Powyższy graf zawiera 6 wierzchołków, więc będziemy kontynuować relaksację aż do 5 wierzchołków. Tutaj rozluźnimy wszystkie krawędzie 5 razy. Pętla wykona iterację 5 razy, aby uzyskać poprawną odpowiedź. Jeśli pętla zostanie powtórzona więcej niż 5 razy, to również odpowiedź będzie taka sama, tj. odległość między wierzchołkami nie ulegnie zmianie.
Relaks oznacza:
różnica między lisem a wilkiem
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
Zatem odległość wierzchołka B wynosi 6.
Rozważmy krawędź (A, C). Oznacz wierzchołek „A” jako „u”, a wierzchołek „C” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Ponieważ (0 + 4) jest mniejsze niż ∞, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Zatem odległość wierzchołka C wynosi 4.
Rozważmy krawędź (A, D). Oznacz wierzchołek „A” jako „u”, a wierzchołek „D” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Ponieważ (0 + 5) jest mniejsze niż ∞, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Zatem odległość wierzchołka D wynosi 5.
Rozważmy krawędź (B, E). Oznacz wierzchołek „B” jako „u”, a wierzchołek „E” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Ponieważ (6 - 1) jest mniejsze niż ∞, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Zatem odległość wierzchołka E wynosi 5.
Rozważmy krawędź (C, E). Oznacz wierzchołek „C” jako „u” i wierzchołek „E” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 4
d(v) = 5
c(u, v) = 3
Ponieważ (4 + 3) jest większe niż 5, więc nie będzie aktualizacji. Wartość w wierzchołku E wynosi 5.
Rozważmy krawędź (D, C). Oznacz wierzchołek „D” jako „u”, a wierzchołek „C” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 5
d(v) = 4
c(u, v) = -2
Ponieważ (5 -2) jest mniejsze niż 4, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Zatem odległość wierzchołka C wynosi 3.
Rozważmy krawędź (D, F). Oznacz wierzchołek „D” jako „u” i wierzchołek „F” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Ponieważ (5 -1) jest mniejsze niż ∞, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Zatem odległość wierzchołka F wynosi 4.
tablica obiektów w Javie
Rozważmy krawędź (E, F). Oznacz wierzchołek „E” jako „u” i wierzchołek „F” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Ponieważ (5 + 3) jest większe niż 4, więc nie będzie aktualizacji wartości odległości wierzchołka F.
Rozważmy krawędź (C, B). Oznacz wierzchołek „C” jako „u”, a wierzchołek „B” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 3
d(v) = 6
c(u, v) = -2
Ponieważ (3 - 2) jest mniejsze niż 6, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Zatem odległość wierzchołka B wynosi 1.
Teraz pierwsza iteracja została zakończona. Przechodzimy do drugiej iteracji.
Druga iteracja:
W drugiej iteracji ponownie sprawdzamy wszystkie krawędzie. Pierwsza krawędź to (A, B). Ponieważ (0 + 6) jest większe niż 1, więc nie byłoby aktualizacji w wierzchołku B.
Następna krawędź to (A, C). Ponieważ (0 + 4) jest większe niż 3, więc nie byłoby aktualizacji w wierzchołku C.
Następna krawędź to (A, D). Ponieważ (0 + 5) równa się 5, więc nie byłoby aktualizacji w wierzchołku D.
Następna krawędź to (B, E). Ponieważ (1 - 1) równa się 0, czyli mniej niż 5, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B, E)
= 1 - 1 = 0
Następna krawędź to (C, E). Ponieważ (3 + 3) równa się 6, czyli jest większe niż 5, zatem nie byłoby aktualizacji w wierzchołku E.
Następna krawędź to (D, C). Ponieważ (5 - 2) równa się 3, więc nie byłoby aktualizacji w wierzchołku C.
Następna krawędź to (D, F). Ponieważ (5 - 1) równa się 4, więc nie byłoby aktualizacji w wierzchołku F.
Następna krawędź to (E, F). Ponieważ (5 + 3) równa się 8, czyli jest większe niż 4, zatem nie byłoby aktualizacji w wierzchołku F.
Następna krawędź to (C, B). Ponieważ (3 - 2) równa się 1`, zatem nie byłoby aktualizacji w wierzchołku B.
Trzecia iteracja
Wykonamy te same kroki, co w poprzednich iteracjach. Zaobserwujemy, że nie będzie aktualizacji odległości wierzchołków.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Złożoność czasu
Złożoność czasowa algorytmu Bellmana Forda będzie wynosić 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
Zatem odległość wierzchołka 3 wynosi 5.
Rozważmy krawędź (1, 2). Oznacz wierzchołek „1” jako „u”, a wierzchołek „2” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Ponieważ (0 + 4) jest mniejsze niż ∞, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Zatem odległość wierzchołka 2 wynosi 4.
Rozważmy krawędź (3, 2). Oznacz wierzchołek „3” jako „u”, a wierzchołek „2” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 5
d(v) = 4
c(u, v) = 7
Zastępowanie metody w Javie
Ponieważ (5 + 7) jest większe niż 4, więc w wierzchołku 2 nie będzie aktualizacji.
Rozważmy krawędź (2, 4). Oznacz wierzchołek „2” jako „u”, a wierzchołek „4” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Ponieważ (4 + 7) równa się 11, czyli mniej niż ∞, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Zatem odległość wierzchołka 4 wynosi 11.
Rozważmy krawędź (4, 3). Oznacz wierzchołek „4” jako „u”, a wierzchołek „3” jako „v”. Teraz użyj relaksującej formuły:
d(u) = 11
d(v) = 5
c(u, v) = -15
Ponieważ (11 - 15) równa się -4, czyli mniej niż 5, więc zaktualizuj
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Zatem odległość wierzchołka 3 wynosi -4.
Teraz przechodzimy do drugiej iteracji.
Druga iteracja
Teraz ponownie sprawdzimy wszystkie krawędzie. Pierwsza krawędź to (1, 3). Ponieważ (0 + 5) równa się 5, czyli jest większe niż -4, więc nie byłoby aktualizacji w wierzchołku 3.
Następna krawędź to (1, 2). Ponieważ (0 + 4) równa się 4, więc nie byłoby aktualizacji w wierzchołku 2.
Następna krawędź to (3, 2). Ponieważ (-4 + 7) równa się 3, czyli mniej niż 4, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Dlatego wartość w wierzchołku 2 wynosi 3.
Następna krawędź to (2, 4). Ponieważ ( 3+7) równa się 10, czyli mniej niż 11, więc zaktualizuj
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Dlatego wartość w wierzchołku 4 wynosi 10.
FCFS
Następna krawędź to (4, 3). Ponieważ (10 - 15) równa się -5, czyli mniej niż -4, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Dlatego wartość w wierzchołku 3 wynosi -5.
Teraz przechodzimy do trzeciej iteracji.
Trzecia iteracja
Teraz ponownie sprawdzimy wszystkie krawędzie. Pierwsza krawędź to (1, 3). Ponieważ (0 + 5) równa się 5, czyli jest większe niż -5, więc nie byłoby aktualizacji w wierzchołku 3.
Następna krawędź to (1, 2). Ponieważ (0 + 4) równa się 4, czyli jest większe niż 3, zatem nie byłoby aktualizacji w wierzchołku 2.
Następna krawędź to (3, 2). Ponieważ (-5 + 7) równa się 2, czyli mniej niż 3, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Dlatego wartość w wierzchołku 2 wynosi 2.
Następna krawędź to (2, 4). Ponieważ (2 + 7) równa się 9, czyli mniej niż 10, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Dlatego wartość w wierzchołku 4 wynosi 9.
Następna krawędź to (4, 3). Ponieważ (9 - 15) równa się -6, czyli mniej niż -5, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Dlatego wartość w wierzchołku 3 wynosi -6.
Ponieważ graf zawiera 4 wierzchołki, więc zgodnie z algorytmem Bellmana Forda będą tylko 3 iteracje. Jeśli spróbujemy wykonać 4titeracji na wykresie, odległość wierzchołków od danego wierzchołka nie powinna się zmieniać. Jeśli odległość jest różna, oznacza to, że algorytm Bellmana Forda nie podaje prawidłowej odpowiedzi.
4titeracja
Pierwsza krawędź to (1, 3). Ponieważ (0 +5) równa się 5, które jest większe niż -6, zatem nie byłoby zmiany w wierzchołku 3.
Następna krawędź to (1, 2). Ponieważ (0 + 4) jest większe niż 2, więc nie byłoby aktualizacji.
Następna krawędź to (3, 2). Ponieważ (-6 + 7) równa się 1, czyli mniej niż 3, więc zaktualizuj:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
W tym przypadku wartość wierzchołka jest aktualizowana. Dochodzimy zatem do wniosku, że algorytm Bellmana Forda nie działa, gdy wykres zawiera cykl ujemnych wag.
Dlatego wartość w wierzchołku 2 wynosi 1.