Bellman ford algoritms ir viena avota īsākā ceļa algoritms. Šis algoritms tiek izmantots, lai atrastu īsāko attālumu no vienas virsotnes līdz visām pārējām svērtā grafika virsotnēm. Īsākā ceļa atrašanai tiek izmantoti dažādi citi algoritmi, piemēram, Dijkstra algoritms utt. Ja svērtajā grafikā ir negatīvās svara vērtības, Dijkstra algoritms neapstiprina, vai tas rada pareizo atbildi vai nē. Atšķirībā no Dijkstra algoritma, Belman ford algoritms garantē pareizo atbildi pat tad, ja svērtajā grafikā ir ietvertas negatīvās svara vērtības.
Šī algoritma noteikums
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Apsveriet tālāk redzamo grafiku:
Iepriekš redzamajā grafikā redzams, ka daži svari ir negatīvi. Iepriekš minētajā grafikā ir 6 virsotnes, tāpēc mēs turpināsim atpūsties līdz 5 virsotnēm. Šeit mēs atslābināsim visas malas 5 reizes. Lai iegūtu pareizo atbildi, cilpa atkārtosies 5 reizes. Ja cilpa tiek atkārtota vairāk nekā 5 reizes, tad arī atbilde būs tāda pati, t.i., attālums starp virsotnēm nemainītos.
Relaksācija nozīmē:
diskrētās matemātikas noliegums
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
Tāpēc virsotnes B attālums ir 6.
Apsveriet malu (A, C). Apzīmējiet virsotni 'A' kā 'u' un virsotni 'C' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Tā kā (0 + 4) ir mazāks par ∞, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Tāpēc virsotnes C attālums ir 4.
Apsveriet malu (A, D). Apzīmējiet virsotni 'A' kā 'u' un virsotni 'D' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 0
d(v) = ∞
c(u , v) = 5
Tā kā (0 + 5) ir mazāks par ∞, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Tāpēc virsotnes D attālums ir 5.
Apsveriet malu (B, E). Apzīmējiet virsotni 'B' kā 'u' un virsotni 'E' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 6
d(v) = ∞
c(u , v) = -1
Tā kā (6 - 1) ir mazāks par ∞, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 6 - 1 = 5
Tāpēc virsotnes E attālums ir 5.
Apsveriet malu (C, E). Apzīmējiet virsotni 'C' kā 'u' un virsotni 'E' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 4
d(v) = 5
c(u , v) = 3
Tā kā (4 + 3) ir lielāks par 5, tāpēc atjauninājums netiks veikts. Vērtība virsotnē E ir 5.
Apsveriet malu (D, C). Apzīmējiet virsotni 'D' kā 'u' un virsotni 'C' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 5
d(v) = 4
c(u , v) = -2
Tā kā (5 -2) ir mazāks par 4, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Tāpēc virsotnes C attālums ir 3.
Apsveriet malu (D, F). Apzīmējiet virsotni 'D' kā 'u' un virsotni 'F' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 5
d(v) = ∞
c(u , v) = -1
Tā kā (5 -1) ir mazāks par ∞, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Tāpēc virsotnes F attālums ir 4.
Apsveriet malu (E, F). Apzīmējiet virsotni 'E' kā 'u' un virsotni 'F' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 5
d(v) = ∞
c(u , v) = 3
Tā kā (5 + 3) ir lielāks par 4, tad virsotnes F attāluma vērtība netiks atjaunināta.
Apsveriet malu (C, B). Apzīmējiet virsotni 'C' kā 'u' un virsotni 'B' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 3
d(v) = 6
c(u , v) = -2
Tā kā (3–2) ir mazāks par 6, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Tāpēc virsotnes B attālums ir 1.
Tagad pirmā iterācija ir pabeigta. Mēs pārietam uz otro atkārtojumu.
Otrā iterācija:
python generē uuid
Otrajā atkārtojumā mēs vēlreiz pārbaudām visas malas. Pirmā mala ir (A, B). Tā kā (0 + 6) ir lielāks par 1, virsotnē B nebūtu nekādu atjauninājumu.
Nākamā mala ir (A, C). Tā kā (0 + 4) ir lielāks par 3, tad virsotnē C nebūtu nekādu atjaunināšanu.
Nākamā mala ir (A, D). Tā kā (0 + 5) ir vienāds ar 5, tāpēc virsotnē D nebūtu atjauninājumu.
Nākamā mala ir (B, E). Tā kā (1 - 1) ir vienāds ar 0, kas ir mazāks par 5, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
d(E) = d(B) + c(B , E)
= 1 - 1 = 0
Nākamā mala ir (C, E). Tā kā (3 + 3) ir vienāds ar 6, kas ir lielāks par 5, tāpēc virsotnē E nebūtu nekādu atjauninājumu.
Nākamā mala ir (D, C). Tā kā (5 - 2) ir vienāds ar 3, tāpēc virsotnē C nebūtu atjauninājumu.
Nākamā mala ir (D, F). Tā kā (5 - 1) ir vienāds ar 4, tāpēc virsotnē F nebūtu atjauninājumu.
Nākamā mala ir (E, F). Tā kā (5 + 3) ir vienāds ar 8, kas ir lielāks par 4, tāpēc virsotnē F nebūtu nekādu atjauninājumu.
Nākamā mala ir (C, B). Tā kā (3 - 2) ir vienāds ar 1`, virsotnē B nebūtu atjauninājumu.
Trešā iterācija
Mēs veiksim tās pašas darbības kā iepriekšējās iterācijās. Mēs ievērosim, ka virsotņu attālumā nebūs atjauninājumu.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Laika sarežģītība
Belmana forda algoritma laika sarežģītība būtu 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
Tāpēc 3. virsotnes attālums ir 5.
Apsveriet malu (1, 2). Apzīmējiet virsotni '1' kā 'u' un virsotni '2' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 0
d(v) = ∞
c(u , v) = 4
Tā kā (0 + 4) ir mazāks par ∞, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Tāpēc 2. virsotnes attālums ir 4.
Apsveriet malu (3, 2). Apzīmējiet virsotni '3' kā 'u' un virsotni '2' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 5
d(v) = 4
c(u , v) = 7
Tā kā (5 + 7) ir lielāks par 4, tātad virsotnē 2 nebūtu atjauninājumu.
Apsveriet malu (2, 4). Apzīmējiet virsotni '2' kā 'u' un virsotni '4' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 4
d(v) = ∞
c(u , v) = 7
Tā kā (4 + 7) ir vienāds ar 11, kas ir mazāks par ∞, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Tāpēc 4. virsotnes attālums ir 11.
Apsveriet malu (4, 3). Apzīmējiet virsotni '4' kā 'u' un virsotni '3' kā 'v'. Tagad izmantojiet relaksācijas formulu:
d(u) = 11
d(v) = 5
c(u , v) = -15
Tā kā (11–15) ir vienāds ar -4, kas ir mazāks par 5, tāpēc atjauniniet
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Tāpēc 3. virsotnes attālums ir -4.
Tagad mēs pārejam uz otro atkārtojumu.
Otrā iterācija
Tagad mēs atkal pārbaudīsim visas malas. Pirmā mala ir (1, 3). Tā kā (0 + 5) ir vienāds ar 5, kas ir lielāks par -4, tāpēc virsotnē 3 nebūtu nekādu atjauninājumu.
Nākamā mala ir (1, 2). Tā kā (0 + 4) ir vienāds ar 4, tāpēc virsotnē 2 nebūtu nekādu atjauninājumu.
Nākamā mala ir (3, 2). Tā kā (-4 + 7) ir vienāds ar 3, kas ir mazāks par 4, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
vlc multivides atskaņotāja lejupielāde youtube
d(2) = d(3) + c(3, 2)
= -4 + 7 = 3
Tāpēc vērtība virsotnē 2 ir 3.
Nākamā mala ir (2, 4). Tā kā (3+7) ir vienāds ar 10, kas ir mazāks par 11, tāpēc atjauniniet
d(v) = d(u) + c(u, v)
d(4) = d(2) + c(2, 4)
= 3 + 7 = 10
Tāpēc vērtība virsotnē 4 ir 10.
java virkne satur
Nākamā mala ir (4, 3). Tā kā (10–15) ir vienāds ar -5, kas ir mazāks par -4, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
d(3) = d(4) + c(4, 3)
= 10 - 15 = -5
Tāpēc vērtība virsotnē 3 ir -5.
Tagad mēs pārejam uz trešo atkārtojumu.
Trešā iterācija
Tagad atkal pārbaudīsim visas malas. Pirmā mala ir (1, 3). Tā kā (0 + 5) ir vienāds ar 5, kas ir lielāks par -5, tāpēc virsotnē 3 nebūtu nekādu atjauninājumu.
Nākamā mala ir (1, 2). Tā kā (0 + 4) ir vienāds ar 4, kas ir lielāks par 3, tāpēc virsotnē 2 nebūtu atjauninājumu.
Nākamā mala ir (3, 2). Tā kā (-5 + 7) ir vienāds ar 2, kas ir mazāks par 3, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
d(2) = d(3) + c(3, 2)
= -5 + 7 = 2
Tāpēc vērtība virsotnē 2 ir 2.
Nākamā mala ir (2, 4). Tā kā (2 + 7) ir vienāds ar 9, kas ir mazāks par 10, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
d(4) = d(2) + c(2, 4)
= 2 + 7 = 9
Tāpēc vērtība virsotnē 4 ir 9.
Nākamā mala ir (4, 3). Tā kā (9 - 15) ir vienāds ar -6, kas ir mazāks par -5, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
d(3) = d(4) + c(4, 3)
= 9 - 15 = -6
Tāpēc vērtība virsotnē 3 ir -6.
Tā kā grafikā ir 4 virsotnes, tad saskaņā ar Belmana forda algoritmu būtu tikai 3 iterācijas. Ja mēģinām izpildīt 4thiterācijas grafikā, virsotņu attālumam no dotās virsotnes nevajadzētu mainīties. Ja attālums mainās, tas nozīmē, ka Belman ford algoritms nesniedz pareizo atbildi.
4thiterācija
Pirmā mala ir (1, 3). Tā kā (0 +5) ir vienāds ar 5, kas ir lielāks par -6, tāpēc virsotnē 3 nebūtu nekādu izmaiņu.
Nākamā mala ir (1, 2). Tā kā (0 + 4) ir lielāks par 2, atjaunināšana nenotiks.
Nākamā mala ir (3, 2). Tā kā (-6 + 7) ir vienāds ar 1, kas ir mazāks par 3, tāpēc atjauniniet:
d(v) = d(u) + c(u, v)
d(2) = d(3) + c(3, 2)
= -6 + 7 = 1
Šajā gadījumā virsotnes vērtība tiek atjaunināta. Tātad, mēs secinām, ka Belmana forda algoritms nedarbojas, ja grafikā ir ietverts negatīvais svara cikls.
Tāpēc vērtība virsotnē 2 ir 1.