GRAPH ALGORITHMS : C PROGRAM for BELLMANFORD DETECTING negative(-ve) CYCLE WITH USER INPUT

 C PROGRAM TO IMPLEMENT BELLMANFORD DETECTING -VE CYCLE WITH USER INPUT 

 #include <stdio.h>

#include <stdlib.h>

#define INFINITY 99999

struct Edge {

    int u;

    int v;

    int w;

};

struct Graph {

    int V;

    int E;

    struct Edge *edge;

};

void bellmanford(struct Graph *g, int source);

void display(int arr[], int size);

int main(void){

int i;

    struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));

    printf("Enter number of edges : ");

    scanf("%d",&g->E);

    printf("\nEnter number of vertices : ");

    scanf("%d",&g->V);

    g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));

    for(i=0;i<g->E;i++){

        printf("Enter vertices and weight value of edge %d : ",i+1);

        scanf("%d %d %d",&g->edge[i].u,&g->edge[i].v,&g->edge[i].w);

    }

    bellmanford(g, 0);

    return 0;

}

void bellmanford(struct Graph *g, int source) {

    int i, j, u, v, w;

    int tV = g->V;

    int tE = g->E;

    int d[tV];

    int p[tV];

    for (i = 0; i < tV; i++) {

        d[i] = INFINITY;

        p[i] = 0;

    }

    d[source] = 0;

    for (i = 1; i <= tV - 1; i++) {

        for (j = 0; j < tE; j++) {

            u = g->edge[j].u;

            v = g->edge[j].v;

            w = g->edge[j].w;

            if (d[u] != INFINITY && d[v] > d[u] + w) {

                d[v] = d[u] + w;

                p[v] = u;

            }

        }

    }

    for (i = 0; i < tE; i++) {

        u = g->edge[i].u;

        v = g->edge[i].v;

        w = g->edge[i].w;

        if (d[u] != INFINITY && d[v] > d[u] + w) {

            printf("Negative weight cycle detected!");

            printf("Edge value are %d %d %d",u,v,w);

            return;

        }

    }

    printf("Distance array: ");

    display(d, tV);

    printf("Predecessor array: ");

    display(p, tV);

}

void display(int arr[], int size) {

    int i;

    for (i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

}

Output :