To understand the implementation of Bellman Ford's Algorithm using C++
Objective
To understand the implementation of Bellman Ford's Algorithm using C++
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void printArr(int dist[], int n) {
cout << "\nVertex | Distance from Source\n";
for (int i = 0; i < n; ++i)
cout<< i <<" \t | \t\t "<< dist[i]<< "\n";
}
void BellmanFord(struct Graph* graph, int src) {
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V-1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
cout<<"Graph contains negative weight cycle";
return;
}
}
printArr(dist, V);
return;
}
int main() {
int V, E;
cout << "Enter number of vertices: ";
cin>>V;
cout<< "Enter number of edges: ";
cin>>E;
struct Graph* graph = createGraph(V, E);
for(int i=0; i < E; i++) {
cout << "Enter source vertex, destination vertex and weight for edge "<< i+1<<": ";
cin>>graph->edge[i].src>>graph->edge[i].dest>>graph->edge[i].weight;
}
BellmanFord(graph, 0);
return 0;
}
Discussion of Algorithm
- Start
- Set the distance of the source vertex to 0 and all other vertices to infinity.
- For each vertex, apply relaxation for all the edges.
- Repeat step 3 for V-1 times.
- Perform step 3 one more time and if any distance is updated then the graph has a negative cycle.
- End
Representations
Flow Diagram
+----------------------------------+ | | | Start | | | | +----------------------------------+ | V +----------------------------------+ | | | int V, E; | | | | +----------------------------------+ | V +----------------------------------+ | | | Create the graph structure | | and input the data | | | | struct Graph* graph = | | createGraph(V, E); | | cin>>graph->edge[i].src>> | | graph->edge[i].dest>> | | graph->edge[i].weight; | | | +----------------------------------+ | V +----------------------------------+ | | | Bellman-Ford Algorithm | | (Single Source Shortest Path) | | | | int dist[V]; | | dist[src] = 0; | | Perform relaxation steps | | Check for negative weight | | cycles | | | +----------------------------------+ | V +----------------------------------+ | | | Print the distances | | from the source vertex | | | +----------------------------------+ | V +----------------------------------+ | | | Exit | | | | +----------------------------------+
Tabular Dry Run
Iteration | Distance | Updated Distance |
---|---|---|
1 | 0 | 0 |
1 | 1 | -1 |
1 | 2 | 4 |
1 | 3 | 2 |
1 | 4 | 2 |
2 | 2 | 2 |
2 | 3 | -1 |
Output
Enter number of vertices: 5 Enter number of edges: 8 Enter source vertex, destination vertex and weight for edge 1: 0 1 -1 Enter source vertex, destination vertex and weight for edge 2: 0 2 4 Enter source vertex, destination vertex and weight for edge 3: 1 2 3 Enter source vertex, destination vertex and weight for edge 4: 1 3 2 Enter source vertex, destination vertex and weight for edge 5: 1 4 2 Enter source vertex, destination vertex and weight for edge 6: 3 2 5 Enter source vertex, destination vertex and weight for edge 7: 3 1 1 Enter source vertex, destination vertex and weight for edge 8: 4 3 -3 Vertex | Distance from Source 0 | 0 1 | -1 2 | 2 3 | -2 4 | 1