10      3
   A ──────► B ─────► D
    \       /  ↖↑     / ↘
   2  \  5 /     1   /   6
      ↘  ↙       ↙  /
       C ───4──► E ───7──► F

#include<stdio.h>
#include<stdbool.h>
#define V 6
#define INF 99999

typedef struct {
    int u, v, wt;
} Edge;

void bellmanFord(Edge edges[], int E, int src) {
    int dist[V], parent[V];
    for(int i=0; i<V; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }
    dist[src] = 0;

    // Relax all edges V-1 times
    for(int i=1; i<=V-1; i++) {
        bool updated = false;
        for(int j=0; j<E; j++) {
            int u = edges[j].u;
            int v = edges[j].v;
            int wt = edges[j].wt;
            if(dist[u] != INF && dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt;
                parent[v] = u;
                updated = true;
            }
        }
        if(!updated) {
            printf("No updates in iteration %d → Early termination\n", i);
            break;
        }
    }

    // Check for negative cycle
    bool negCycle = false;
    for(int j=0; j<E; j++) {
        int u = edges[j].u;
        int v = edges[j].v;
        int wt = edges[j].wt;
        if(dist[u] != INF && dist[u] + wt < dist[v]) {
            printf("Negative cycle detected via edge %c→%c\n", 'A'+u, 'A'+v);
            negCycle = true;
        }
    }

    if(!negCycle) {
        printf("Final Shortest Distances from A:\n");
        for(int i=0; i<V; i++)
            printf("%c → %d\n", 'A'+i, dist[i]);
    }
}

int main() {
    Edge edges[] = {
        {0,1,10}, {0,2,2}, {1,3,3}, {1,4,1},
        {2,4,4}, {3,5,6}, {4,5,7}
    };
    int E = 7;

    printf("Bellman-Ford (No negative cycle):\n");
    bellmanFord(edges, E, 0);

    // Add negative cycle
    printf("\nAdding F→B(-10) → Negative cycle test:\n");
    Edge edges2[] = {
        {0,1,10}, {0,2,2}, {1,3,3}, {1,4,1},
        {2,4,4}, {3,5,6}, {4,5,7}, {5,1,-10}
    };
    bellmanFord(edges2, 8, 0);

    return 0;
}

Bellman-Ford (No negative cycle):
Final Shortest Distances from A:
A → 0
B → 10
C → 2
D → 13
E → 6
F → 13

Adding F→B(-10) → Negative cycle test:
Negative cycle detected via edge F→B