L'algoritmo di Bellman Ford è un algoritmo del percorso più breve a sorgente singola. Questo algoritmo viene utilizzato per trovare la distanza più breve dal singolo vertice a tutti gli altri vertici di un grafico pesato. Esistono vari altri algoritmi utilizzati per trovare il percorso più breve come l'algoritmo Dijkstra, ecc. Se il grafico ponderato contiene valori di peso negativi, l'algoritmo Dijkstra non conferma se produce la risposta corretta o meno. A differenza dell'algoritmo di Dijkstra, l'algoritmo di Bellman Ford garantisce la risposta corretta anche se il grafico pesato contiene valori di peso negativi.
Regola di questo algoritmo
We will go on relaxing all the edges (n - 1) times where, n = number of vertices
Considera il grafico seguente:
Come possiamo osservare nel grafico sopra, alcuni pesi sono negativi. Il grafico sopra contiene 6 vertici quindi continueremo a rilassarci fino ai 5 vertici. Qui rilasseremo tutti i bordi 5 volte. Il ciclo ripeterà 5 volte per ottenere la risposta corretta. Se il ciclo viene ripetuto più di 5 volte, anche la risposta sarà la stessa, ovvero non ci sarebbe alcun cambiamento nella distanza tra i vertici.
Rilassarsi significa:
Linux Mint Cannella vs Mate
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
Pertanto, la distanza del vertice B è 6.
Considera il bordo (A, C). Denota il vertice 'A' come 'u' e il vertice 'C' come 'v'. Ora usa la formula rilassante:
d(u) = 0
d(v) = ∞
c(u, v) = 4
Poiché (0 + 4) è inferiore a ∞, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Pertanto la distanza del vertice C è 4.
Considera il bordo (A, D). Denota il vertice 'A' come 'u' e il vertice 'D' come 'v'. Ora usa la formula rilassante:
d(u) = 0
d(v) = ∞
c(u, v) = 5
Poiché (0 + 5) è inferiore a ∞, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 0 + 5 = 5
Pertanto la distanza del vertice D è 5.
Considera il bordo (B, E). Denota il vertice 'B' come 'u' e il vertice 'E' come 'v'. Ora usa la formula rilassante:
d(u) = 6
d(v) = ∞
c(u, v) = -1
Poiché (6 - 1) è inferiore a ∞, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 6 - 1= 5
Pertanto la distanza del vertice E è 5.
Considera il bordo (C, E). Denota il vertice 'C' come 'u' e il vertice 'E' come 'v'. Ora usa la formula rilassante:
d(u) = 4
d(v) = 5
c(u, v) = 3
Poiché (4 + 3) è maggiore di 5, non ci sarà alcun aggiornamento. Il valore al vertice E è 5.
Considera il bordo (D, C). Denota il vertice 'D' come 'u' e il vertice 'C' come 'v'. Ora usa la formula rilassante:
d(u) = 5
d(v) = 4
c(u, v) = -2
Poiché (5 -2) è inferiore a 4, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3
Pertanto la distanza del vertice C è 3.
Considera il bordo (D, F). Denota il vertice 'D' come 'u' e il vertice 'F' come 'v'. Ora usa la formula rilassante:
d(u) = 5
d(v) = ∞
c(u, v) = -1
Poiché (5 -1) è inferiore a ∞, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 5 - 1 = 4
Pertanto la distanza del vertice F è 4.
Considera il bordo (E, F). Denota il vertice 'E' come 'u' e il vertice 'F' come 'v'. Ora usa la formula rilassante:
d(u) = 5
d(v) = ∞
c(u, v) = 3
Poiché (5 + 3) è maggiore di 4, non ci sarebbe alcun aggiornamento sul valore della distanza del vertice F.
Considera il bordo (C, B). Denota il vertice 'C' come 'u' e il vertice 'B' come 'v'. Ora usa la formula rilassante:
pseudocodice Java
d(u) = 3
d(v) = 6
c(u, v) = -2
Poiché (3 - 2) è inferiore a 6, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 3 - 2 = 1
Pertanto, la distanza del vertice B è 1.
Ora la prima iterazione è completata. Passiamo alla seconda iterazione.
Seconda iterazione:
Nella seconda iterazione, controlliamo nuovamente tutti i bordi. Il primo bordo è (A, B). Poiché (0 + 6) è maggiore di 1, non ci sarebbe alcun aggiornamento nel vertice B.
Il bordo successivo è (A, C). Poiché (0 + 4) è maggiore di 3, non ci sarebbe alcun aggiornamento nel vertice C.
Il bordo successivo è (A, D). Poiché (0 + 5) è uguale a 5 quindi non ci sarebbe alcun aggiornamento nel vertice D.
Il bordo successivo è (B, E). Poiché (1 - 1) è uguale a 0 che è inferiore a 5, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
= 1 - 1 = 0
Il bordo successivo è (C, E). Poiché (3 + 3) è uguale a 6 che è maggiore di 5 quindi non ci sarebbe alcun aggiornamento nel vertice E.
Il bordo successivo è (D, C). Poiché (5 - 2) è uguale a 3 quindi non ci sarebbe alcun aggiornamento nel vertice C.
Il bordo successivo è (D, F). Poiché (5 - 1) è uguale a 4 quindi non ci sarebbe alcun aggiornamento nel vertice F.
Il bordo successivo è (E, F). Poiché (5 + 3) è uguale a 8 che è maggiore di 4 quindi non ci sarebbe alcun aggiornamento nel vertice F.
Il bordo successivo è (C, B). Poiché (3 - 2) è uguale a 1`, non ci sarebbe alcun aggiornamento nel vertice B.
Terza iterazione
Eseguiremo gli stessi passaggi che abbiamo eseguito nelle iterazioni precedenti. Osserveremo che non ci sarà alcun aggiornamento nella distanza dei vertici.
The following are the distances of vertices: A: 0 B: 1 C: 3 D: 5 E: 0 F: 3
Complessità temporale
La complessità temporale dell'algoritmo di Bellman Ford sarebbe 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
Pertanto, la distanza del vertice 3 è 5.
Consideriamo il bordo (1, 2). Denota il vertice '1' come 'u' e il vertice '2' come 'v'. Ora usa la formula rilassante:
strati del modello osi
d(u) = 0
d(v) = ∞
c(u, v) = 4
Poiché (0 + 4) è inferiore a ∞, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4
Pertanto la distanza del vertice 2 è 4.
Consideriamo il bordo (3, 2). Denota il vertice '3' come 'u' e il vertice '2' come 'v'. Ora usa la formula rilassante:
d(u) = 5
d(v) = 4
c(u, v) = 7
Poiché (5 + 7) è maggiore di 4, non ci sarebbe alcun aggiornamento nel vertice 2.
Consideriamo il bordo (2, 4). Denota il vertice '2' come 'u' e il vertice '4' come 'v'. Ora usa la formula rilassante:
d(u) = 4
d(v) = ∞
c(u, v) = 7
Poiché (4 + 7) equivale a 11 che è inferiore a ∞, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 4 + 7 = 11
Pertanto la distanza del vertice 4 è 11.
Consideriamo il bordo (4, 3). Denota il vertice '4' come 'u' e il vertice '3' come 'v'. Ora usa la formula rilassante:
d(u) = 11
d(v) = 5
c(u, v) = -15
Poiché (11 - 15) equivale a -4 che è inferiore a 5, quindi aggiorna
d(v) = d(u) + c(u , v)
d(v) = 11 - 15 = -4
Pertanto, la distanza del vertice 3 è -4.
Passiamo ora alla seconda iterazione.
Seconda iterazione
Ora controlleremo ancora una volta tutti i bordi. Il primo arco è (1, 3). Poiché (0 + 5) è uguale a 5 che è maggiore di -4, non ci sarebbe alcun aggiornamento nel vertice 3.
Il bordo successivo è (1, 2). Poiché (0 + 4) è uguale a 4, non ci sarebbe alcun aggiornamento nel vertice 2.
Il bordo successivo è (3, 2). Poiché (-4 + 7) equivale a 3 che è inferiore a 4, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -4 + 7 = 3
Pertanto, il valore al vertice 2 è 3.
Il bordo successivo è (2, 4). Poiché (3+7) equivale a 10 che è inferiore a 11, quindi aggiorna
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 3 + 7 = 10
Pertanto, il valore al vertice 4 è 10.
PD unire
Il bordo successivo è (4, 3). Poiché (10 - 15) è uguale a -5 che è inferiore a -4, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 10 - 15 = -5
Pertanto, il valore al vertice 3 è -5.
Passiamo ora alla terza iterazione.
Terza iterazione
Ora controlleremo ancora una volta tutti i bordi. Il primo arco è (1, 3). Poiché (0 + 5) è uguale a 5 che è maggiore di -5, non ci sarebbe alcun aggiornamento nel vertice 3.
Il bordo successivo è (1, 2). Poiché (0 + 4) è uguale a 4 che è maggiore di 3, non ci sarebbe alcun aggiornamento nel vertice 2.
Il bordo successivo è (3, 2). Poiché (-5 + 7) equivale a 2 che è inferiore a 3, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -5 + 7 = 2
Pertanto, il valore al vertice 2 è 2.
Il bordo successivo è (2, 4). Poiché (2 + 7) equivale a 9 che è inferiore a 10, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(4) = d(2) +c(2, 4)
= 2 + 7 = 9
Pertanto, il valore al vertice 4 è 9.
Il bordo successivo è (4, 3). Poiché (9 - 15) è uguale a -6 che è inferiore a -5, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(3) = d(4) +c(4, 3)
= 9 - 15 = -6
Pertanto, il valore al vertice 3 è -6.
Poiché il grafico contiene 4 vertici, secondo l'algoritmo di Bellman Ford, ci sarebbero solo 3 iterazioni. Se proviamo a eseguire 4thiterazione sul grafico, la distanza dei vertici dal vertice dato non dovrebbe cambiare. Se la distanza varia significa che l'algoritmo di Bellman Ford non fornisce la risposta corretta.
4thiterazione
Il primo arco è (1, 3). Poiché (0 +5) è uguale a 5 che è maggiore di -6, non ci sarebbe alcun cambiamento nel vertice 3.
Il bordo successivo è (1, 2). Poiché (0 + 4) è maggiore di 2, non ci sarebbe alcun aggiornamento.
Il bordo successivo è (3, 2). Poiché (-6 + 7) equivale a 1 che è inferiore a 3, quindi aggiorna:
d(v) = d(u) + c(u, v)
d(2) = d(3) +c(3, 2)
= -6 + 7 = 1
In questo caso, il valore del vertice viene aggiornato. Quindi, concludiamo che l'algoritmo di Bellman Ford non funziona quando il grafico contiene il ciclo di peso negativo.
Pertanto, il valore al vertice 2 è 1.