INPUT GRAPH:
SOURCE CODE:
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
struct Edge
{
int src, dest, weight;
};
void printDistances(const vector<int>& dist, int V)
{
for (int i = 0; i < V; ++i)
{
if (dist[i] == INT_MAX)
cout << "INF\t";
else
cout << dist[i] << "\t";
}
cout << "\n";
}
void BellmanFord(const vector<Edge>& edges, int V, int E, int src)
{
vector<int> dist(V, INT_MAX);
dist[src] = 0;
cout << "Iteration wise distances:\n";
cout << "Iteration 0: ";
printDistances(dist, V);
for (int i = 1; i <= V - 1; ++i)
{
for (int j = 0; j < E; ++j)
{
int u = edges[j].src;
int v = edges[j].dest;
int weight = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
{
dist[v] = dist[u] + weight;
}
}
cout << "Iteration " << i << ": ";
printDistances(dist, V);
}
for (int i = 0; i < E; ++i)
{
int u = edges[i].src;
int v = edges[i].dest;
int weight = edges[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
{
cout << "Graph contains negative weight cycle\n";
return;
}
}
cout << "\nFinal distances from source:\n";
printDistances(dist, V);
}
int main()
{
int V, E;
cout << "Enter the number of vertices: ";
cin >> V;
cout << "Enter the number of edges: ";
cin >> E;
vector<Edge> edges(E);
cout << "Enter the edges with their weights (source destination weight):\n";
for (int i = 0; i < E; ++i)
{
cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
}
int src;
cout << "Enter the source vertex: ";
cin >> src;
BellmanFord(edges, V, E, src);
return 0;
}
INPUT AND OUTPUT:
OUTPUT GRAPH:
