|
| 1 | +# Bellman-Ford |
| 2 | + |
| 3 | +#### Problem Statement |
| 4 | + |
| 5 | +Given a weighted directed graph G(V,E) and a source vertex s ∈ V, determine for each vertex v ∈ V the shortest path between s and v. |
| 6 | + |
| 7 | +#### Approach |
| 8 | + |
| 9 | +- Initialize the distance from the source to all vertices as infinite. |
| 10 | +- Initialize the distance to itself as 0. |
| 11 | +- Create an array dist[] of size |V| with all values as infinite except dist[s]. |
| 12 | +- Repeat the following |V| - 1 times. Where |V| is number of vertices. |
| 13 | +- Create another loop to go through each edge (u, v) in E and do the following: |
| 14 | + 1. dist[v] = minimum(dist[v], dist[u] + weight of edge). |
| 15 | +- Lastly iterate through all edges on last time to make sure there are no negatively weighted cycles. |
| 16 | + |
| 17 | +#### Time Complexity |
| 18 | + |
| 19 | +O(VE) |
| 20 | + |
| 21 | +#### Space Complexity |
| 22 | + |
| 23 | +O(V^2) |
| 24 | + |
| 25 | +#### Founder's Name |
| 26 | + |
| 27 | +- Richard Bellman & Lester Ford, Jr. |
| 28 | + |
| 29 | +#### Example |
| 30 | + |
| 31 | +``` |
| 32 | + # of vertices in graph = 5 [A, B, C, D, E] |
| 33 | + # of edges in graph = 8 |
| 34 | +
|
| 35 | + edges [A->B, A->C, B->C, B->D, B->E, D->C, D->B, E->D] |
| 36 | + weight [ -1, 4, 3, 2, 2, 5, 1, -4 ] |
| 37 | + source [ A, A, B, B, B, D, D, E ] |
| 38 | +
|
| 39 | +
|
| 40 | +
|
| 41 | + // edge A->B |
| 42 | + graph->edge[0].src = A |
| 43 | + graph->edge[0].dest = B |
| 44 | + graph->edge[0].weight = -1 |
| 45 | + |
| 46 | + // edge A->C |
| 47 | + graph->edge[1].src = A |
| 48 | + graph->edge[1].dest = C |
| 49 | + graph->edge[1].weight = 4 |
| 50 | + |
| 51 | + // edge B->C |
| 52 | + graph->edge[2].src = B |
| 53 | + graph->edge[2].dest = C |
| 54 | + graph->edge[2].weight = 3 |
| 55 | + |
| 56 | + // edge B->D |
| 57 | + graph->edge[3].src = B |
| 58 | + graph->edge[3].dest = D |
| 59 | + graph->edge[3].weight = 2 |
| 60 | + |
| 61 | + // edge B->E |
| 62 | + graph->edge[4].src = B |
| 63 | + graph->edge[4].dest = E |
| 64 | + graph->edge[4].weight = 2 |
| 65 | + |
| 66 | + // edge D->C |
| 67 | + graph->edge[5].src = D |
| 68 | + graph->edge[5].dest = C |
| 69 | + graph->edge[5].weight = 5 |
| 70 | + |
| 71 | + // edge D->B |
| 72 | + graph->edge[6].src = D |
| 73 | + graph->edge[6].dest = B |
| 74 | + graph->edge[6].weight = 1 |
| 75 | + |
| 76 | + // edge E->D |
| 77 | + graph->edge[7].src = E
DF37
|
| 78 | + graph->edge[7].dest = D |
| 79 | + graph->edge[7].weight = -3 |
| 80 | +
|
| 81 | + for source = A |
| 82 | +
|
| 83 | + Vertex Distance from Source |
| 84 | + A 0 A->A |
| 85 | + B -1 A->B |
| 86 | + C 2 A->B->C = -1 + 3 |
| 87 | + D -2 A->B->E->D = -1 + 2 + -3 |
| 88 | + E 1 A->B->E = -1 + 2 |
| 89 | + ``` |
| 90 | + |
| 91 | + |
| 92 | +#### Code Implementation Links |
| 93 | + |
| 94 | +- [Java](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Graphs/BellmanFord.java) |
| 95 | +- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Dynamic%20Programming/Bellman-Ford.cpp) |
| 96 | +- [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/graph/bellman_ford.py) |
| 97 | +- [C](https://github.com/TheAlgorithms/C/blob/master/data_structures/graphs/Bellman-Ford.c) |
| 98 | + |
| 99 | +#### Video Explanation |
| 100 | + |
| 101 | +[A video explaining the Bellman-Ford Algorithm](https://www.youtube.com/watch?v=hxMWBBCpR6A) |
| 102 | + |
| 103 | +#### Others |
| 104 | + |
| 105 | +Sources Used: |
| 106 | +- https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ |
| 107 | +- https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm |
0 commit comments