Bellman Ford in C

BellmanFord.c

#include <stdio.h>
#include <limits.h>
#define MAX 100

int INFINITY = INT_MAX;

struct Edge{
    int u, v, weight;
};

void bellman_ford(int weights[MAX][MAX], int n, int s){
    int max_no_of_edges = n*n, index = 0, total_cost = 0;
    struct Edge edges[max_no_of_edges];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(weights[i][j] == INFINITY)        continue;
            edges[index].u = i;
            edges[index].v = j;
            edges[index].weight = weights[i][j];
            index++;
        }
    }
    int no_of_edges = index;
    
    int dist[MAX], prev[MAX];
    for(int i=0;i<n;i++){
        dist[i] = INFINITY;
        prev[i] = -1;
    }
    dist[s] = 0;
    
    for(int z=0;z<(n-1);z++){
        for(int i=0;i<no_of_edges;i++){
            int u = edges[i].u ,v = edges[i].v, weight = edges[i].weight;
            if( (dist[u]==INFINITY) || (weight==INFINITY) )      continue;
            if(dist[u] + weight < dist[v]){
                dist[v] = dist[u] + weight;
                prev[v] = u;
            }
        }
    }
    for(int i=0;i<no_of_edges;i++){
        int u = edges[i].u ,v = edges[i].v, weight = edges[i].weight;
        if(dist[u]==INFINITY || weight==INFINITY )      continue;
        if(dist[u] + weight < dist[v]){
            printf("Error..\n");
            printf("Negative weight cycle present in graph..\n");
            return;
        }
    }
    printf("Vertex: ");
    for(int i=0;i<n;i++){
        printf("%d ", (i+1));
    }
    printf("\n");
    printf("Distance: ");
    for(int i=0;i<n;i++){
        printf("%d ", dist[i]);
    }
    printf("\n");
    printf("Prev: ");
    for(int i=0;i<n;i++){
        printf("%d ", prev[i]+1);
    }
    printf("\n");
    
    
}

int main() {
    int n, s, matrix[MAX][MAX];
    // Take inputs
    printf("Enter no of vertex: ");
    scanf("%d", &n);
    printf("Enter edges & weights one by one: \n");
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d", &matrix[i][j]);
            // 0 --> Infinity
            if(matrix[i][j] == 0)       matrix[i][j] = INFINITY;
        }
    }
    printf("Enter source vertex: \n");
    scanf("%d", &s);
    
    bellman_ford(matrix, n, s-1);
    
    return 0;
}
/*
5
0 0 6 3 0
3 0 0 0 0
0 0 0 2 0
0 1 1 0 0
0 4 0 2 0
5
*/