#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 6 // Number of vertices
#define E 9 // Number of edges
// Structure to represent an edge
struct Edge {
int src, dest, weight;
};
// Function to implement Bellman-Ford algorithm
void BellmanFord(struct Edge* edges, int source) {
int dist[V];
int i, j;
// Initialize distances
for (i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[source] = 0;
// Relax all edges V-1 times
for (i = 1; i <= V - 1; i++) {
for (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;
}
}
// Check for negative-weight cycles
for (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]) {
printf("Graph contains negative weight cycle\n");
return;
}
}
// Print the distances
printf("Vertex Distance from Source\n");
for (i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
int main() {struct Edge edges[E] = {
{0, 1, -4}, {0, 3, -3}, {1, 2, -2},
{1, 3, 4}, {2, 4, 2}, {2, 5, 1},
{3, 1, 1}, {3, 4, 5}, {4, 5, -3}
};
BellmanFord(edges, 0); // 0 is the source vertex
return 0;
}