Bellman ford algoritmas yra vieno šaltinio trumpiausio kelio algoritmas. Šis algoritmas naudojamas norint rasti trumpiausią atstumą nuo vienos viršūnės iki visų kitų svertinio grafiko viršūnių. Trumpiausiam keliui rasti naudojami įvairūs kiti algoritmai, pvz., Dijkstra algoritmas ir tt Jei svertiniame grafike yra neigiamos svorio reikšmės, Dijkstra algoritmas nepatvirtina, ar jis pateikia teisingą atsakymą, ar ne. Priešingai nei Dijkstra algoritmas, bellman ford algoritmas garantuoja teisingą atsakymą, net jei svertiniame grafike yra neigiamos svorio reikšmės.
Šio algoritmo taisyklė
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Apsvarstykite žemiau pateiktą grafiką:
Kaip matome aukščiau esančiame grafike, kai kurie svoriai yra neigiami. Aukščiau pateiktame grafike yra 6 viršūnės, todėl atsipalaiduosime iki 5 viršūnių. Čia atpalaiduosime visus kraštus 5 kartus. Ciklas kartosis 5 kartus, kad gautų teisingą atsakymą. Jei ciklas kartojamas daugiau nei 5 kartus, atsakymas taip pat bus toks pat, ty atstumas tarp viršūnių nepasikeistų.
Atsipalaidavimas reiškia:
daliniai latekso dariniai
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
Todėl viršūnės B atstumas yra 6.
Apsvarstykite kraštą (A, C). Viršūnę „A“ pažymėkite kaip „u“, o viršūnę „C“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Kadangi (0 + 4) yra mažesnis nei ∞, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Todėl viršūnės C atstumas yra 4.
Apsvarstykite kraštą (A, D). Viršūnę „A“ pažymėkite kaip „u“, o viršūnę „D“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 0
d(v) = ∞
c(u , v) = 5
Kadangi (0 + 5) yra mažesnis nei ∞, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Todėl viršūnės D atstumas yra 5.
Apsvarstykite kraštą (B, E). Viršūnę „B“ pažymėkite kaip „u“, o viršūnę „E“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 6
d(v) = ∞
c(u , v) = -1
Kadangi (6 - 1) yra mažesnis nei ∞, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Todėl viršūnės E atstumas yra 5.
Apsvarstykite kraštą (C, E). Viršūnę „C“ pažymėkite kaip „u“, o viršūnę „E“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 4
d(v) = 5
c(u , v) = 3
Kadangi (4 + 3) yra didesnis nei 5, tai atnaujinimo nebus. Vertė viršūnėje E yra 5.
Apsvarstykite kraštą (D, C). Pažymėkite viršūnę „D“ kaip „u“, o viršūnę „C“ kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 5
d(v) = 4
c(u , v) = -2
Kadangi (5 -2) yra mažesnis nei 4, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Todėl viršūnės C atstumas yra 3.
Apsvarstykite kraštą (D, F). Viršūnę „D“ pažymėkite kaip „u“, o viršūnę „F“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 5
d(v) = ∞
base64 javascript dekodavimas
c(u , v) = -1
Kadangi (5 -1) yra mažesnis nei ∞, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Todėl viršūnės F atstumas yra 4.
Apsvarstykite kraštą (E, F). Viršūnę „E“ pažymėkite kaip „u“, o viršūnę „F“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 5
d(v) = ∞
c(u , v) = 3
Kadangi (5 + 3) yra didesnis nei 4, todėl viršūnės F atstumo reikšmė nebūtų atnaujinta.
Apsvarstykite kraštą (C, B). Pažymėkite viršūnę „C“ kaip „u“, o viršūnę „B“ kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 3
d(v) = 6
c(u , v) = -2
Kadangi (3 - 2) yra mažesnis nei 6, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Todėl viršūnės B atstumas yra 1.
Dabar pirmoji iteracija baigta. Mes pereiname prie antrojo kartojimo.
Antroji iteracija:
Antroje iteracijoje vėl patikriname visus kraštus. Pirmasis kraštas yra (A, B). Kadangi (0 + 6) yra didesnis nei 1, viršūnėje B atnaujinimo nebūtų.
Kitas kraštas yra (A, C). Kadangi (0 + 4) yra didesnis nei 3, viršūnėje C atnaujinimo nebūtų.
Kitas kraštas yra (A, D). Kadangi (0 + 5) yra lygus 5, todėl viršūnėje D nebūtų atnaujinimo.
Kitas kraštas yra (B, E). Kadangi (1–1) yra lygus 0, kuris yra mažesnis nei 5, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
Kitas kraštas yra (C, E). Kadangi (3 + 3) yra lygus 6, kuris yra didesnis nei 5, todėl viršūnėje E nebūtų atnaujinimo.
Kitas kraštas yra (D, C). Kadangi (5 - 2) yra lygus 3, todėl viršūnėje C atnaujinimo nebūtų.
Kitas kraštas yra (D, F). Kadangi (5 - 1) yra lygus 4, todėl viršūnėje F nebūtų atnaujinimo.
Kitas kraštas yra (E, F). Kadangi (5 + 3) yra lygus 8, kuris yra didesnis nei 4, todėl viršūnėje F nebūtų atnaujinimo.
Kitas kraštas yra (C, B). Kadangi (3 - 2) lygus 1`, viršūnėje B nebūtų atnaujinimo.
Trečias pakartojimas
Atliksime tuos pačius veiksmus, kaip ir ankstesnėse iteracijose. Stebėsime, kad viršūnių atstumo atnaujinimo nebus.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Laiko sudėtingumas
Bellman Ford algoritmo laiko sudėtingumas būtų 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
Todėl 3 viršūnės atstumas yra 5.
Apsvarstykite kraštą (1, 2). Pažymėkite viršūnę „1“ kaip „u“, o viršūnę „2“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Kadangi (0 + 4) yra mažesnis nei ∞, todėl atnaujinkite
stygų metodai java
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Todėl 2 viršūnės atstumas yra 4.
Apsvarstykite kraštą (3, 2). Pažymėkite viršūnę „3“ kaip „u“, o viršūnę „2“ kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 5
d(v) = 4
c(u , v) = 7
Kadangi (5 + 7) yra didesnis nei 4, todėl 2 viršūnėje atnaujinimo nebūtų.
Apsvarstykite kraštą (2, 4). Pažymėkite viršūnę „2“ kaip „u“, o viršūnę „4“ kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 4
d(v) = ∞
c(u , v) = 7
Kadangi (4 + 7) yra lygus 11, kuris yra mažesnis nei ∞, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Todėl 4 viršūnės atstumas yra 11.
Apsvarstykite kraštą (4, 3). Viršūnę „4“ pažymėkite kaip „u“, o viršūnę „3“ – kaip „v“. Dabar naudokite atpalaidavimo formulę:
d(u) = 11
d(v) = 5
c(u , v) = -15
Kadangi (11–15) yra lygus -4, kuris yra mažesnis nei 5, todėl atnaujinkite
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Todėl 3 viršūnės atstumas yra -4.
Dabar pereiname prie antrosios iteracijos.
Antra iteracija
Dabar dar kartą patikrinsime visus kraštus. Pirmasis kraštas yra (1, 3). Kadangi (0 + 5) yra lygus 5, kuris yra didesnis nei -4, todėl 3 viršūnėje nebus atnaujinimo.
Kitas kraštas yra (1, 2). Kadangi (0 + 4) yra lygus 4, taigi 2 viršūnėje nebūtų jokių atnaujinimų.
Kitas kraštas yra (3, 2). Kadangi (-4 + 7) yra lygus 3, kuris yra mažesnis nei 4, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Todėl vertė 2 viršūnėje yra 3.
Kitas kraštas yra (2, 4). Kadangi ( 3 + 7) yra 10, tai yra mažiau nei 11, todėl atnaujinkite
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Todėl vertė 4 viršūnėje yra 10.
Greatandhra
Kitas kraštas yra (4, 3). Kadangi (10–15) yra lygus -5, kuris yra mažesnis nei -4, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Todėl vertė 3 viršūnėje yra -5.
Dabar pereiname prie trečiosios iteracijos.
Trečias pakartojimas
Dabar dar kartą patikrinsime visus kraštus. Pirmasis kraštas yra (1, 3). Kadangi (0 + 5) yra lygus 5, kuris yra didesnis nei -5, todėl 3 viršūnėje nebus atnaujinimo.
Kitas kraštas yra (1, 2). Kadangi (0 + 4) yra lygus 4, kuris yra didesnis nei 3, todėl 2 viršūnėje nebus atnaujinimo.
Kitas kraštas yra (3, 2). Kadangi (-5 + 7) yra lygus 2, kuris yra mažesnis nei 3, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Todėl vertė 2 viršūnėje yra 2.
Kitas kraštas yra (2, 4). Kadangi (2 + 7) yra lygus 9, kuris yra mažesnis nei 10, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Todėl vertė 4 viršūnėje yra 9.
Kitas kraštas yra (4, 3). Kadangi (9 - 15) yra lygus -6, kuris yra mažesnis nei -5, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Todėl vertė 3 viršūnėje yra -6.
Kadangi grafe yra 4 viršūnės, tai pagal Belman ford algoritmą būtų tik 3 iteracijos. Jei bandysime atlikti 4thiteracija grafike, viršūnių atstumas nuo nurodytos viršūnės neturėtų keistis. Jei atstumas skiriasi, tai reiškia, kad bellman ford algoritmas nepateikia teisingo atsakymo.
4thiteracija
Pirmasis kraštas yra (1, 3). Kadangi (0 +5) yra lygus 5, kuris yra didesnis nei -6, todėl viršūnė 3 nepasikeis.
Kitas kraštas yra (1, 2). Kadangi (0 + 4) yra didesnis nei 2, atnaujinimo nebus.
Kitas kraštas yra (3, 2). Kadangi (-6 + 7) yra lygus 1, kuris yra mažesnis nei 3, todėl atnaujinkite:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
Tokiu atveju viršūnės reikšmė atnaujinama. Taigi darome išvadą, kad bellman ford algoritmas neveikia, kai grafike yra neigiamas svorio ciklas.
Todėl vertė 2 viršūnėje yra 1.