1. Initialize:
   dist[source] = 0
   dist[others] = ∞

2. Relax all edges V-1 times:
   for i = 1 to V-1:
       for each edge (u,v,w):
           if dist[u] + w < dist[v]:
               dist[v] = dist[u] + w
               parent[v] = u

3. Check for negative cycle:
   for each edge (u,v,w):
       if dist[u] + w < dist[v]:
           → Negative cycle exists!

    A
   / \  
  6   -2
 /     \
B-------C
  \    / \
   7  4   5
    \ |   |
     D----E
       -3

Now: E → B (-10) → C (7) → D (4) → E (-3) = -12 < 0 → Negative Cycle!

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5
#define INF INT_MAX

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

typedef struct {
    Edge edges[100];
    int E;  // Number of edges
} Graph;

Graph* createGraph() {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->E = 0;
    return g;
}

void addEdge(Graph* g, int u, int v, int w) {
    g->edges[g->E].u = u;
    g->edges[g->E].v = v;
    g->edges[g->E++].w = w;
}

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

    // Relax V-1 times
    for(int i = 1; i <= V-1; i++) {
        int updated = 0;
        for(int j = 0; j < g->E; j++) {
            int u = g->edges[j].u;
            int v = g->edges[j].v;
            int w = g->edges[j].w;

            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                updated = 1;
            }
        }
        if (!updated) break;  // Early termination
    }

    // Check negative cycle
    for(int j = 0; j < g->E; j++) {
        int u = g->edges[j].u;
        int v = g->edges[j].v;
        int w = g->edges[j].w;

        if (dist[u] != INF && dist[u] + w < dist[v]) {
            printf("Negative cycle detected!\n");
            return;
        }
    }

    // Print result
    printf("Vertex\tDistance\tPath\n");
    for(int i = 0; i < V; i++) {
        printf("%c \t", 'A' + i);
        if(dist[i] == INF) printf("INF\t-\n");
        else {
            printf("%d\t", dist[i]);
            // Print path (recursive)
            int temp = i;
            while(temp != -1) {
                printf("%c ", 'A' + temp);
                temp = parent[temp];
                if(temp != -1) printf("← ");
            }
            printf("\n");
        }
    }
}

// Main
int main() {
    Graph* g = createGraph();

    addEdge(g, 0, 1, 6);   // A→B
    addEdge(g, 0, 2, -2);  // A→C
    addEdge(g, 1, 2, 7);   // B→C
    addEdge(g, 1, 3, 7);   // B→D
    addEdge(g, 2, 3, 4);   // C→D
    addEdge(g, 2, 4, 5);   // C→E
    addEdge(g, 3, 4, -3);  // D→E

    printf("Bellman-Ford (Source = A)\n");
    bellmanFord(g, 0);

    return 0;
}

Bellman-Ford (Source = A)
Vertex  Distance       Path
A       0               A 
B       6               B ← A 
C       -2              C ← A 
D       2               D ← C ← A 
E       -1              E ← D ← C ← A 

Iteration 1:
A→B: 0+6 < ∞ → B=6
A→C: 0-2 < ∞ → C=-2
C→D: -2+4 → D=2
C→E: -2+5 → E=7

Iteration 2:
D→E: 2 + (-3) = -1 < 7 → E=-1

No change in Iteration 3 → Done

addEdge(g, 4, 1, -10);  // E→B (-10)

E→B: -1 + (-10) = -11 < 6 → Update B!
→ Infinite loop possible → Negative cycle!

Use queue + inQueue[] array
Only relax nodes that were updated
Average: O(E), Worst: O(V×E)