Алгоритм Беллмана Форда — це алгоритм найкоротшого шляху з одним джерелом. Цей алгоритм використовується для знаходження найкоротшої відстані від однієї вершини до всіх інших вершин зваженого графа. Існують різні інші алгоритми, які використовуються для пошуку найкоротшого шляху, як-от алгоритм Дейкстри тощо. Якщо зважений графік містить від’ємні значення ваги, тоді алгоритм Дейкстри не підтверджує, чи дає правильну відповідь чи ні. На відміну від алгоритму Дейкстри, алгоритм Беллмана Форда гарантує правильну відповідь, навіть якщо зважений графік містить негативні значення ваги.
Правило цього алгоритму
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Розгляньте наведений нижче графік:
Як ми бачимо на наведеному вище графіку, деякі вагові коефіцієнти є від’ємними. Наведений вище граф містить 6 вершин, тому ми продовжимо розслаблятися до 5 вершин. Тут ми розслабимо всі краї 5 разів. Цикл повторюватиметься 5 разів, щоб отримати правильну відповідь. Якщо цикл повторюється більше 5 разів, відповідь буде однаковою, тобто відстань між вершинами не зміниться.
Розслаблюючі засоби:
рівність об’єктів Java
If (d(u) + c(u , v) <d(v)) d(v)="d(u)" + c(u , v) < pre> <p>To find the shortest path of the above graph, the first step is note down all the edges which are given below:</p> <p>(A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B)</p> <p>Let's consider the source vertex as 'A'; therefore, the distance value at vertex A is 0 and the distance value at all the other vertices as infinity shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-2.webp" alt="Bellman-Ford Algorithm"> <p>Since the graph has six vertices so it will have five iterations.</p> <p> <strong>First iteration</strong> </p> <p>Consider the edge (A, B). Denote vertex 'A' as 'u' and vertex 'B' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 6</p> <p>Since (0 + 6) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 6 = 6</p> <p>Therefore, the distance of vertex B is 6.</p> <p>Consider the edge (A, C). Denote vertex 'A' as 'u' and vertex 'C' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 4</p> <p>Since (0 + 4) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 4 = 4</p> <p>Therefore, the distance of vertex C is 4.</p> <p>Consider the edge (A, D). Denote vertex 'A' as 'u' and vertex 'D' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 5</p> <p>Since (0 + 5) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 5 = 5</p> <p>Therefore, the distance of vertex D is 5.</p> <p>Consider the edge (B, E). Denote vertex 'B' as 'u' and vertex 'E' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 6</p> <p>d(v) = ∞</p> <p>c(u , v) = -1</p> <p>Since (6 - 1) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 6 - 1= 5</p> <p>Therefore, the distance of vertex E is 5.</p> <p>Consider the edge (C, E). Denote vertex 'C' as 'u' and vertex 'E' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 4</p> <p>d(v) = 5</p> <p>c(u , v) = 3</p> <p>Since (4 + 3) is greater than 5, so there will be no updation. The value at vertex E is 5.</p> <p>Consider the edge (D, C). Denote vertex 'D' as 'u' and vertex 'C' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 5</p> <p>d(v) = 4</p> <p>c(u , v) = -2</p> <p>Since (5 -2) is less than 4, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 5 - 2 = 3</p> <p>Therefore, the distance of vertex C is 3.</p> <p>Consider the edge (D, F). Denote vertex 'D' as 'u' and vertex 'F' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 5</p> <p>d(v) = ∞</p> <p>c(u , v) = -1</p> <p>Since (5 -1) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 5 - 1 = 4</p> <p>Therefore, the distance of vertex F is 4.</p> <p>Consider the edge (E, F). Denote vertex 'E' as 'u' and vertex 'F' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 5</p> <p>d(v) = ∞</p> <p>c(u , v) = 3</p> <p>Since (5 + 3) is greater than 4, so there would be no updation on the distance value of vertex F.</p> <p>Consider the edge (C, B). Denote vertex 'C' as 'u' and vertex 'B' as 'v'. Now use the relaxing formula:</p> <p>d(u) = 3</p> <p>d(v) = 6</p> <p>c(u , v) = -2</p> <p>Since (3 - 2) is less than 6, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 3 - 2 = 1</p> <p>Therefore, the distance of vertex B is 1.</p> <p>Now the first iteration is completed. We move to the second iteration.</p> <p> <strong>Second iteration:</strong> </p> <p>In the second iteration, we again check all the edges. The first edge is (A, B). Since (0 + 6) is greater than 1 so there would be no updation in the vertex B.</p> <p>The next edge is (A, C). Since (0 + 4) is greater than 3 so there would be no updation in the vertex C.</p> <p>The next edge is (A, D). Since (0 + 5) equals to 5 so there would be no updation in the vertex D.</p> <p>The next edge is (B, E). Since (1 - 1) equals to 0 which is less than 5 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(E) = d(B) +c(B , E)</p> <p>= 1 - 1 = 0</p> <p>The next edge is (C, E). Since (3 + 3) equals to 6 which is greater than 5 so there would be no updation in the vertex E.</p> <p>The next edge is (D, C). Since (5 - 2) equals to 3 so there would be no updation in the vertex C.</p> <p>The next edge is (D, F). Since (5 - 1) equals to 4 so there would be no updation in the vertex F.</p> <p>The next edge is (E, F). Since (5 + 3) equals to 8 which is greater than 4 so there would be no updation in the vertex F.</p> <p>The next edge is (C, B). Since (3 - 2) equals to 1` so there would be no updation in the vertex B.</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-3.webp" alt="Bellman-Ford Algorithm"> <p> <strong>Third iteration</strong> </p> <p>We will perform the same steps as we did in the previous iterations. We will observe that there will be no updation in the distance of vertices.</p> <pre> The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3 </pre> <p> <strong>Time Complexity</strong> </p> <p>The time complexity of Bellman ford algorithm would be O(E|V| - 1).</p> <pre> function bellmanFord(G, S) for each vertex V in G distance[V] <- 0 infinite previous[v] <- null distance[s] for each vertex v in g edge (u,v) tempdistance distance[u] + edge_weight(u, v) if < distance[v] u distance[v} error: negative cycle exists return distance[], previous[] pre> <p> <strong>Drawbacks of Bellman ford algorithm</strong> </p> <ul> <li>The bellman ford algorithm does not produce a correct answer if the sum of the edges of a cycle is negative. Let's understand this property through an example. Consider the below graph. <br> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-4.webp" alt="Bellman-Ford Algorithm"></li> <li>In the above graph, we consider vertex 1 as the source vertex and provides 0 value to it. We provide infinity value to other vertices shown as below: <br> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-5.webp" alt="Bellman-Ford Algorithm"> <br>Edges can be written as: <br> (1, 3), (1, 2), (2, 4), (3, 2), (4, 3) </li> </ul> <p> <strong>First iteration</strong> </p> <p> <strong>Consider the edge (1, 3). Denote vertex '1' as 'u' and vertex '3' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 5</p> <p>Since (0 + 5) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 5 = 5</p> <p>Therefore, the distance of vertex 3 is 5.</p> <p> <strong>Consider the edge (1, 2). Denote vertex '1' as 'u' and vertex '2' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 0</p> <p>d(v) = ∞</p> <p>c(u , v) = 4</p> <p>Since (0 + 4) is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 0 + 4 = 4</p> <p>Therefore, the distance of vertex 2 is 4.</p> <p> <strong>Consider the edge (3, 2). Denote vertex '3' as 'u' and vertex '2' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 5</p> <p>d(v) = 4</p> <p>c(u , v) = 7</p> <p>Since (5 + 7) is greater than 4, so there would be no updation in the vertex 2.</p> <p> <strong>Consider the edge (2, 4). Denote vertex '2' as 'u' and vertex '4' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 4</p> <p>d(v) = ∞</p> <p>c(u , v) = 7</p> <p>Since (4 + 7) equals to 11 which is less than ∞, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 4 + 7 = 11</p> <p>Therefore, the distance of vertex 4 is 11.</p> <p> <strong>Consider the edge (4, 3). Denote vertex '4' as 'u' and vertex '3' as 'v'. Now use the relaxing formula:</strong> </p> <p>d(u) = 11</p> <p>d(v) = 5</p> <p>c(u , v) = -15</p> <p>Since (11 - 15) equals to -4 which is less than 5, so update</p> <pre> d(v) = d(u) + c(u , v) </pre> <p>d(v) = 11 - 15 = -4</p> <p>Therefore, the distance of vertex 3 is -4.</p> <p>Now we move to the second iteration.</p> <p> <strong>Second iteration</strong> </p> <p>Now, again we will check all the edges. The first edge is (1, 3). Since (0 + 5) equals to 5 which is greater than -4 so there would be no updation in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) equals to 4 so there would be no updation in the vertex 2.</p> <p>The next edge is (3, 2). Since (-4 + 7) equals to 3 which is less than 4 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -4 + 7 = 3</p> <p>Therefore, the value at vertex 2 is 3.</p> <p>The next edge is (2, 4). Since ( 3+7) equals to 10 which is less than 11 so update</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(4) = d(2) +c(2, 4)</p> <p>= 3 + 7 = 10</p> <p>Therefore, the value at vertex 4 is 10.</p> <p>The next edge is (4, 3). Since (10 - 15) equals to -5 which is less than -4 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(3) = d(4) +c(4, 3)</p> <p>= 10 - 15 = -5</p> <p>Therefore, the value at vertex 3 is -5.</p> <p>Now we move to the third iteration.</p> <p> <strong>Third iteration</strong> </p> <p>Now again we will check all the edges. The first edge is (1, 3). Since (0 + 5) equals to 5 which is greater than -5 so there would be no updation in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) equals to 4 which is greater than 3 so there would be no updation in the vertex 2.</p> <p>The next edge is (3, 2). Since (-5 + 7) equals to 2 which is less than 3 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -5 + 7 = 2</p> <p>Therefore, the value at vertex 2 is 2.</p> <p>The next edge is (2, 4). Since (2 + 7) equals to 9 which is less than 10 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(4) = d(2) +c(2, 4)</p> <p>= 2 + 7 = 9</p> <p>Therefore, the value at vertex 4 is 9.</p> <p>The next edge is (4, 3). Since (9 - 15) equals to -6 which is less than -5 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(3) = d(4) +c(4, 3)</p> <p>= 9 - 15 = -6</p> <p>Therefore, the value at vertex 3 is -6.</p> <img src="//techcodeview.com/img/daa-tutorial/85/bellman-ford-algorithm-6.webp" alt="Bellman-Ford Algorithm"> <p>Since the graph contains 4 vertices, so according to the bellman ford algorithm, there would be only 3 iterations. If we try to perform 4<sup>th</sup> iteration on the graph, the distance of the vertices from the given vertex should not change. If the distance varies, it means that the bellman ford algorithm is not providing the correct answer.</p> <p> <strong>4<sup>th</sup> iteration</strong> </p> <p>The first edge is (1, 3). Since (0 +5) equals to 5 which is greater than -6 so there would be no change in the vertex 3.</p> <p>The next edge is (1, 2). Since (0 + 4) is greater than 2 so there would be no updation.</p> <p>The next edge is (3, 2). Since (-6 + 7) equals to 1 which is less than 3 so update:</p> <p>d(v) = d(u) + c(u, v)</p> <p>d(2) = d(3) +c(3, 2)</p> <p>= -6 + 7 = 1</p> <p>In this case, the value of the vertex is updated. So, we conclude that the bellman ford algorithm does not work when the graph contains the negative weight cycle.</p> <p>Therefore, the value at vertex 2 is 1.</p> <hr></-></pre></d(v))>
d(v) = 0 + 6 = 6
Отже, відстань вершини B дорівнює 6.
Розглянемо ребро (A, C). Позначимо вершину «A» як «u», а вершину «C» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Оскільки (0 + 4) менше ∞, оновіть
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Отже, відстань вершини C дорівнює 4.
Розглянемо ребро (A, D). Позначимо вершину «A» як «u», а вершину «D» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 0
d(v) = ∞
c(u , v) = 5
Оскільки (0 + 5) менше ∞, оновіть
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Отже, відстань вершини D дорівнює 5.
Розглянемо ребро (B, E). Позначимо вершину «B» як «u», а вершину «E» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 6
d(v) = ∞
c(u , v) = -1
Оскільки (6 - 1) менше за ∞, тому оновіть
d(v) = d(u) + c(u , v)
d(v) = 6 - 1= 5
Отже, відстань вершини E дорівнює 5.
Розглянемо ребро (C, E). Позначимо вершину «C» як «u», а вершину «E» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 4
d(v) = 5
c(u , v) = 3
Оскільки (4 + 3) більше за 5, оновлення не буде. Значення у вершині E дорівнює 5.
Розглянемо ребро (D, C). Позначимо вершину «D» як «u», а вершину «C» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 5
d(v) = 4
c(u , v) = -2
Оскільки (5 -2) менше 4, оновіть
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Отже, відстань вершини C дорівнює 3.
Розглянемо ребро (D, F). Позначимо вершину «D» як «u», а вершину «F» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 5
d(v) = ∞
c(u , v) = -1
Оскільки (5 -1) менше за ∞, тому оновіть
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Отже, відстань вершини F дорівнює 4.
Розглянемо ребро (E, F). Позначимо вершину «E» як «u», а вершину «F» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 5
d(v) = ∞
c(u , v) = 3
Оскільки (5 + 3) більше за 4, значення відстані вершини F не буде оновлено.
Розглянемо ребро (C, B). Позначимо вершину «C» як «u», а вершину «B» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 3
d(v) = 6
c(u , v) = -2
Оскільки (3 - 2) менше 6, тому оновіть
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Отже, відстань вершини B дорівнює 1.
пропустити список
Тепер перша ітерація завершена. Переходимо до другої ітерації.
Друга ітерація:
У другій ітерації ми знову перевіряємо всі ребра. Перше ребро це (A, B). Оскільки (0 + 6) більше за 1, тому у вершині B не буде оновлення.
Наступне ребро (A, C). Оскільки (0 + 4) більше за 3, тому у вершині C не буде оновлення.
Наступне ребро (A, D). Оскільки (0 + 5) дорівнює 5, тому у вершині D не буде оновлення.
Наступне ребро (B, E). Оскільки (1 - 1) дорівнює 0, що менше 5, тому оновіть:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
Наступне ребро (C, E). Оскільки (3 + 3) дорівнює 6, що більше за 5, тому у вершині E не буде оновлення.
Наступне ребро (D, C). Оскільки (5 - 2) дорівнює 3, тому у вершині C не буде оновлення.
Наступне ребро (D, F). Оскільки (5 - 1) дорівнює 4, тому у вершині F не буде оновлення.
Наступне ребро (E, F). Оскільки (5 + 3) дорівнює 8, що більше за 4, тому у вершині F не буде оновлення.
Наступне ребро (C, B). Оскільки (3 - 2) дорівнює 1`, тому у вершині B не буде оновлення.
Третя ітерація
Ми виконаємо ті самі дії, що й у попередніх ітераціях. Ми помітимо, що не буде оновлення відстані між вершинами.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Складність часу
Часова складність алгоритму Беллмана Форда буде 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
Отже, відстань вершини 3 дорівнює 5.
Розглянемо ребро (1, 2). Позначимо вершину «1» як «u», а вершину «2» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Оскільки (0 + 4) менше ∞, оновіть
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Отже, відстань вершини 2 дорівнює 4.
Розглянемо ребро (3, 2). Позначимо вершину «3» як «u», а вершину «2» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 5
d(v) = 4
c(u , v) = 7
Оскільки (5 + 7) більше за 4, тож у вершині 2 не буде оновлення.
Розглянемо ребро (2, 4). Позначимо вершину «2» як «u», а вершину «4» як «v». Тепер використовуйте розслаблюючу формулу:
d(u) = 4
d(v) = ∞
c(u , v) = 7
Оскільки (4 + 7) дорівнює 11, що менше за ∞, тому оновіть
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Отже, відстань вершини 4 дорівнює 11.
Розглянемо ребро (4, 3). Позначимо вершину '4' як 'u', а вершину '3' як 'v'. Тепер використовуйте розслаблюючу формулу:
d(u) = 11
d(v) = 5
c(u , v) = -15
Оскільки (11 - 15) дорівнює -4, що менше 5, тому оновіть
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Отже, відстань вершини 3 дорівнює -4.
Тепер переходимо до другої ітерації.
Друга ітерація
Тепер ще раз перевіримо всі краї. Перше ребро (1, 3). Оскільки (0 + 5) дорівнює 5, що більше за -4, тому у вершині 3 не буде оновлення.
Масив java відсортований
Наступне ребро (1, 2). Оскільки (0 + 4) дорівнює 4, тому у вершині 2 не буде оновлення.
Наступне ребро (3, 2). Оскільки (-4 + 7) дорівнює 3, що менше за 4, оновіть:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Отже, значення у вершині 2 дорівнює 3.
Наступне ребро (2, 4). Оскільки ( 3+7) дорівнює 10, що менше 11, тому оновіть
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Отже, значення у вершині 4 дорівнює 10.
нескінченний цикл
Наступне ребро (4, 3). Оскільки (10 - 15) дорівнює -5, що менше за -4, оновіть:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Отже, значення у вершині 3 дорівнює -5.
Тепер переходимо до третьої ітерації.
Третя ітерація
Тепер ще раз перевіримо всі краї. Перше ребро (1, 3). Оскільки (0 + 5) дорівнює 5, що більше за -5, тому у вершині 3 не буде оновлення.
Наступне ребро (1, 2). Оскільки (0 + 4) дорівнює 4, що більше за 3, тому у вершині 2 не буде оновлення.
Наступне ребро (3, 2). Оскільки (-5 + 7) дорівнює 2, що менше 3, оновіть:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Отже, значення у вершині 2 дорівнює 2.
Наступне ребро (2, 4). Оскільки (2 + 7) дорівнює 9, що менше за 10, оновіть:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Отже, значення у вершині 4 дорівнює 9.
Наступне ребро (4, 3). Оскільки (9 - 15) дорівнює -6, що менше за -5, оновіть:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Отже, значення у вершині 3 дорівнює -6.
Оскільки граф містить 4 вершини, відповідно до алгоритму Беллмана Форда, буде лише 3 ітерації. Якщо ми спробуємо виконати 4тисітерації на графі відстань вершин від заданої вершини не повинна змінюватися. Якщо відстань змінюється, це означає, що алгоритм Bellman Ford не дає правильну відповідь.
4тисітерація
Перше ребро (1, 3). Оскільки (0 +5) дорівнює 5, що більше за -6, тому у вершині 3 не буде змін.
Наступне ребро (1, 2). Оскільки (0 + 4) більше за 2, оновлення не буде.
Наступне ребро (3, 2). Оскільки (-6 + 7) дорівнює 1, що менше 3, оновіть:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
У цьому випадку значення вершини оновлюється. Таким чином, ми робимо висновок, що алгоритм Беллмана Форда не працює, коли графік містить негативний ваговий цикл.
Отже, значення у вершині 2 дорівнює 1.