Bellman ford 알고리즘은 단일 소스 최단 경로 알고리즘입니다. 이 알고리즘은 가중치 그래프의 단일 정점에서 다른 모든 정점까지의 최단 거리를 찾는 데 사용됩니다. Dijkstra 알고리즘 등 최단 경로를 찾는 데 사용되는 다양한 알고리즘이 있습니다. 가중치 그래프에 음의 가중치 값이 포함되어 있으면 Dijkstra 알고리즘은 정답을 생성하는지 여부를 확인하지 않습니다. Dijkstra 알고리즘과 달리 Bellman Ford 알고리즘은 가중치 그래프에 음수 가중치 값이 포함되어 있어도 정답을 보장합니다.
이 알고리즘의 규칙
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
아래 그래프를 고려하십시오.
위 그래프에서 볼 수 있듯이 일부 가중치는 음수입니다. 위 그래프에는 6개의 꼭지점이 포함되어 있으므로 5개의 꼭지점까지 계속 휴식을 취하겠습니다. 여기서는 모든 가장자리를 5번 완화합니다. 루프는 정답을 얻기 위해 5번 반복됩니다. 루프가 5회 이상 반복되면 답도 동일합니다. 즉, 정점 사이의 거리에는 변화가 없습니다.
휴식이란 다음을 의미합니다.
디렉토리 이름 바꾸기
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(유) = 0
d(v) = 무한대
c(유, 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(유) = 0
d(v) = 무한대
c(유, 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(유) = 6
d(v) = 무한대
c(유, 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(유) = 4
d(v) = 5
c(유, v) = 3
(4 + 3)은 5보다 크므로 업데이트가 없습니다. 정점 E의 값은 5입니다.
가장자리 (D, C)를 고려하십시오. 꼭지점 'D'를 'u'로, 꼭지점 'C'를 'v'로 표시합니다. 이제 편안한 공식을 사용하십시오.
d(유) = 5
d(v) = 4
c(유, 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(유) = 5
d(v) = 무한대
c(유, 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(유) = 5
d(v) = 무한대
c(유, v) = 3
(5 + 3)은 4보다 크므로 정점 F의 거리 값은 업데이트되지 않습니다.
가장자리 (C, B)를 고려하십시오. 꼭지점 'C'를 'u'로, 꼭지점 'B'를 'v'로 표시합니다. 이제 편안한 공식을 사용하십시오.
d(유) = 3
d(v) = 6
c(유, 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)은 5보다 큰 6과 같으므로 정점 E에는 업데이트가 없습니다.
다음 간선은 (D, C)입니다. (5 - 2)는 3과 같으므로 정점 C에는 업데이트가 없습니다.
다음 간선은 (D, F)입니다. (5 - 1)은 4와 같으므로 정점 F에는 업데이트가 없습니다.
다음 간선은 (E, F)입니다. (5 + 3)은 4보다 큰 8과 같으므로 정점 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
시간 복잡도
Bellman ford 알고리즘의 시간 복잡도는 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(유) = 0
d(v) = 무한대
c(유, 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(유) = 5
문자열 길이 자바
d(v) = 4
c(유, v) = 7
(5 + 7)은 4보다 크므로 꼭지점 2에는 업데이트가 없습니다.
가장자리(2, 4)를 고려합니다. 꼭지점 '2'를 'u'로, 꼭지점 '4'를 'v'로 표시합니다. 이제 편안한 공식을 사용하십시오.
d(유) = 4
d(v) = 무한대
c(유, v) = 7
(4 + 7)은 11과 같으며 이는 11보다 작으므로 업데이트하십시오.
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
따라서 꼭지점 4의 거리는 11입니다.
가장자리(4, 3)를 고려합니다. 꼭지점 '4'를 'u'로, 꼭지점 '3'을 'v'로 표시합니다. 이제 편안한 공식을 사용하십시오.
d(유) = 11
d(v) = 5
c(유, v) = -15
(11 - 15)는 5보다 작은 -4와 같으므로 업데이트하세요.
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
따라서 꼭지점 3의 거리는 -4입니다.
이제 두 번째 반복으로 넘어갑니다.
두 번째 반복
이제 다시 모든 가장자리를 확인하겠습니다. 첫 번째 간선은 (1, 3)입니다. (0 + 5)는 -4보다 큰 5와 같으므로 정점 3에는 업데이트가 없습니다.
다음 간선은 (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입니다.
fcfs
다음 간선은 (4, 3)입니다. (10 - 15)는 -4보다 작은 -5와 같으므로 업데이트하십시오.
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)는 3보다 큰 4와 같으므로 정점 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개의 꼭지점이 포함되어 있으므로 bellman ford 알고리즘에 따르면 반복은 3번만 수행됩니다. 4번을 수행하려고 하면일그래프를 반복할 때, 주어진 꼭지점으로부터 꼭지점까지의 거리는 변하지 않아야 합니다. 거리가 다르다면 Bellman Ford 알고리즘이 정답을 제공하지 않는다는 의미입니다.
4일반복
첫 번째 간선은 (1, 3)입니다. (0 +5)는 -6보다 큰 5와 같으므로 정점 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
이 경우 정점의 값이 업데이트됩니다. 따라서 우리는 그래프에 음의 가중치 사이클이 포함되어 있으면 bellman ford 알고리즘이 작동하지 않는다는 결론을 내립니다.
따라서 꼭지점 2의 값은 1입니다.