Bellman Ford Algorithm
Given a weighted graph with V vertices and E edges, find the shortest path from a source vertex to all other vertices using the Bellman Ford algorithm.
Constraints:
- The graph can contain negative weight edges.
- The graph does not contain any negative cycles.
- The source vertex is given as an input.
Examples:
Input: [[0, -1, 4], [0, 0, 3], [0, 0, 0], [0, 1, 0]] and source vertex 0
Output: [-1, 0, -2]
Explanation: The shortest path from vertex 0 to vertex 0 is 0, to vertex 1 is -1, and to vertex 2 is -2.
Solutions
Bellman Ford Algorithm
Time: O(VE)Space: O(V)
The Bellman Ford algorithm works by relaxing all edges V-1 times, where V is the number of vertices. After that, it checks for negative weight cycles by trying to relax all edges one more time. If any edge can still be relaxed, then the graph contains a negative weight cycle.
void bellmanFord(vector<vector<int>>& graph, int V, int E, int src) {
vector<int> dist(V, INT_MAX);
dist[src] = 0;
for (int i = 0;
i < V - 1;
i++) {
for (int j = 0;
j < E;
j++) {
int u = graph[j][0];
int v = graph[j][1];
int w = graph[j][2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
for (int i = 0;
i < E;
i++) {
int u = graph[i][0];
int v = graph[i][1];
int w = graph[i][2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
cout << "Graph contains negative weight cycle" << endl;
return;
}
}
for (int i = 0;
i < V;
i++) {
cout << dist[i] << " ";
}
}Follow-up:
How would you modify the Bellman Ford algorithm to handle negative weight cycles?
