Bellmanov fordov algoritem je algoritem najkrajše poti z enim virom. Ta algoritem se uporablja za iskanje najkrajše razdalje od posamezne točke do vseh drugih točk uteženega grafa. Obstajajo različni drugi algoritmi, ki se uporabljajo za iskanje najkrajše poti, kot je Dijkstra algoritem itd. Če tehtani graf vsebuje negativne vrednosti uteži, potem Dijkstra algoritem ne potrdi, ali daje pravilen odgovor ali ne. V nasprotju z algoritmom Dijkstra algoritem bellman ford zagotavlja pravilen odgovor tudi, če uteženi graf vsebuje negativne vrednosti uteži.
Pravilo tega algoritma
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Razmislite o spodnjem grafu:
Kot lahko opazimo na zgornjem grafu, so nekatere uteži negativne. Zgornji graf vsebuje 6 oglišč, tako da se bomo sprostili do 5 oglišč. Tukaj bomo 5-krat sprostili vse robove. Zanka se bo ponovila 5-krat, da bo dobila pravilen odgovor. Če se zanka ponovi več kot 5-krat, bo tudi odgovor enak, tj. ne bo nobene spremembe v razdalji med vozlišči.
Sprostitev pomeni:
nauči se selena
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
Zato je razdalja oglišča B 6.
Upoštevajte rob (A, C). Označite točko 'A' kot 'u' in točko 'C' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Ker je (0 + 4) manj kot ∞, posodobite
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Zato je razdalja oglišča C 4.
Upoštevajte rob (A, D). Točko 'A' označimo z 'u' in točko 'D' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 0
d(v) = ∞
c(u , v) = 5
Ker je (0 + 5) manj kot ∞, posodobite
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Zato je razdalja oglišča D 5.
Upoštevajte rob (B, E). Točko 'B' označimo z 'u' in točko 'E' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 6
d(v) = ∞
c(u , v) = -1
Ker je (6 - 1) manj kot ∞, posodobite
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Zato je razdalja oglišča E 5.
Upoštevajte rob (C, E). Označite točko 'C' kot 'u' in točko 'E' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 4
d(v) = 5
c(u , v) = 3
Ker je (4 + 3) večje od 5, posodobitve ne bo. Vrednost v točki E je 5.
Upoštevajte rob (D, C). Označite točko 'D' kot 'u' in točko 'C' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 5
d(v) = 4
c(u , v) = -2
Ker je (5 -2) manj kot 4, posodobite
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Zato je razdalja oglišča C 3.
Upoštevajte rob (D, F). Točko 'D' označimo kot 'u' in točko 'F' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 5
d(v) = ∞
c(u , v) = -1
Ker je (5 -1) manj kot ∞, posodobite
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Zato je razdalja oglišča F 4.
Upoštevajte rob (E, F). Točko 'E' označimo z 'u' in točko 'F' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 5
d(v) = ∞
c(u , v) = 3
kaj je rom
Ker je (5 + 3) večje od 4, ne bi bilo nobene posodobitve vrednosti razdalje oglišča F.
Upoštevajte rob (C, B). Označite točko 'C' kot 'u' in točko 'B' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 3
d(v) = 6
c(u , v) = -2
Ker je (3 - 2) manj kot 6, posodobite
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Zato je razdalja oglišča B enaka 1.
Zdaj je prva ponovitev končana. Preidemo na drugo ponovitev.
Druga ponovitev:
V drugi ponovitvi ponovno preverimo vse robove. Prvi rob je (A, B). Ker je (0 + 6) večje od 1, v točki B ne bi prišlo do posodobitve.
Naslednji rob je (A, C). Ker je (0 + 4) večje od 3, v točki C ne bi prišlo do posodobitve.
Naslednji rob je (A, D). Ker je (0 + 5) enako 5, v točki D ne bi prišlo do posodobitve.
Naslednji rob je (B, E). Ker je (1 - 1) enako 0, kar je manj kot 5, posodobite:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
Naslednji rob je (C, E). Ker je (3 + 3) enako 6, kar je večje od 5, v točki E ne bi prišlo do posodobitve.
Naslednji rob je (D, C). Ker je (5 - 2) enako 3, v točki C ne bi prišlo do posodobitve.
Naslednji rob je (D, F). Ker je (5 - 1) enako 4, v točki F ne bi prišlo do posodobitve.
Naslednji rob je (E, F). Ker je (5 + 3) enako 8, kar je večje od 4, v točki F ne bi prišlo do posodobitve.
Naslednji rob je (C, B). Ker je (3 - 2) enako 1`, v točki B ne bi prišlo do posodobitve.
Tretja ponovitev
Izvedli bomo enake korake kot v prejšnjih ponovitvah. Opazili bomo, da ne bo prišlo do posodobitve razdalje oglišč.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Časovna zapletenost
Časovna kompleksnost algoritma Bellman Ford bi bila 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
Zato je razdalja oglišča 3 5.
Upoštevajte rob (1, 2). Označite točko '1' kot 'u' in točko '2' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Ker je (0 + 4) manj kot ∞, posodobite
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Zato je razdalja tocke 2 4.
Upoštevajte rob (3, 2). Označite točko '3' kot 'u' in točko '2' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 5
d(v) = 4
c(u , v) = 7
Ker je (5 + 7) večje od 4, v točki 2 ne bi prišlo do posodobitve.
Upoštevajte rob (2, 4). Označite točko '2' kot 'u' in točko '4' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 4
d(v) = ∞
c(u , v) = 7
Ker je (4 + 7) enako 11, kar je manj kot ∞, zato posodobite
kruskalov algoritem
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Zato je razdalja oglišča 4 11.
Upoštevajte rob (4, 3). Označite točko '4' kot 'u' in točko '3' kot 'v'. Zdaj uporabite sproščujočo formulo:
d(u) = 11
d(v) = 5
c(u , v) = -15
Ker je (11 - 15) enako -4, kar je manj kot 5, zato posodobite
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Zato je razdalja oglišča 3 -4.
Zdaj preidemo na drugo ponovitev.
Druga ponovitev
Zdaj bomo ponovno preverili vse robove. Prvi rob je (1, 3). Ker je (0 + 5) enako 5, ki je večje od -4, v točki 3 ne bi prišlo do posodobitve.
Naslednji rob je (1, 2). Ker je (0 + 4) enako 4, v točki 2 ne bi prišlo do posodobitve.
Naslednji rob je (3, 2). Ker je (-4 + 7) enako 3, kar je manj kot 4, posodobite:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Zato je vrednost v točki 2 3.
Naslednji rob je (2, 4). Ker je (3+7) enako 10, kar je manj kot 11, posodobite
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Zato je vrednost v točki 4 10.
prehod pred naročilom
Naslednji rob je (4, 3). Ker je (10 - 15) enako -5, kar je manj kot -4, posodobite:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Zato je vrednost v točki 3 -5.
Zdaj preidemo na tretjo ponovitev.
Tretja ponovitev
Zdaj bomo spet preverili vse robove. Prvi rob je (1, 3). Ker je (0 + 5) enako 5, ki je večje od -5, v točki 3 ne bi prišlo do posodobitve.
Naslednji rob je (1, 2). Ker je (0 + 4) enako 4, ki je večje od 3, v točki 2 ne bi prišlo do posodobitve.
Naslednji rob je (3, 2). Ker je (-5 + 7) enako 2, kar je manj kot 3, posodobite:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Zato je vrednost v točki 2 2.
Naslednji rob je (2, 4). Ker je (2 + 7) enako 9, kar je manj kot 10, posodobite:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Zato je vrednost v točki 4 9.
Naslednji rob je (4, 3). Ker je (9 - 15) enako -6, kar je manj kot -5, posodobite:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Zato je vrednost v točki 3 -6.
Ker graf vsebuje 4 vozlišča, bi bile glede na bellman ford algoritem samo 3 ponovitve. Če poskušamo izvesti 4thponovitve na grafu, se razdalja oglišč od danega oglišča ne sme spremeniti. Če se razdalja spreminja, to pomeni, da algoritem bellman ford ne daje pravilnega odgovora.
4thponovitev
Prvi rob je (1, 3). Ker je (0 +5) enako 5, ki je večje od -6, torej v točki 3 ne bi prišlo do spremembe.
Naslednji rob je (1, 2). Ker je (0 + 4) večje od 2, posodobitve ne bi bilo.
Naslednji rob je (3, 2). Ker je (-6 + 7) enako 1, kar je manj kot 3, posodobite:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
V tem primeru se vrednost oglišča posodobi. Torej sklepamo, da algoritem bellman ford ne deluje, če graf vsebuje cikel negativne teže.
Zato je vrednost v točki 2 1.