#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#include <string.h>
#define MAX 101

int* initGraph(int n) {
    int *graph = (int*) calloc(n*n, sizeof(int));
    return graph;
}

void fillGraph(int *g, int n) {
    srand (time(NULL));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                int r = rand();
                g[i*n + j] = (r < RAND_MAX/2) ? r % 100 : 0;
            }
        }
    }
}

void BellmanFord(int* g, int n, int* distances, int* parents) {

  for (int k = 0; k < n - 1; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i == j || !g[j * n + i]) {
            continue;
        }
        if (distances[i] > distances[j] + g[j * n + i]) {
            distances[i] = distances[j] + g[j * n + i];
            parents[i] = j;
            printf("parents[%d] = %d\n", i, parents[i]);
        }
      }
    }
  }
}

void printGraph(int* g, int n, int* d, int* p) {
    printf("digraph G {\n");

    for (int i = 0; i < n; i++)
        printf("%d [label=\"%d / %d\"];\n", i, i, d[i]);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i*n + j]) {
                if (p[j] == i) {
                    printf("%d -> %d [label=\"%d\", color=\"red\"];\n", i, j, g[i*n + j]);
                } else {
                    printf("%d -> %d [label=\"%d\"];\n", j, i, g[i*n + j]);
                }

            }
        }
    }
    printf("}");
}

int main(void) {
    int n = 10;

    int s = 0;
    int t = 9;

    int *g = initGraph(n);

    fillGraph(g, n);
    int* distances = (int*) malloc (sizeof(int) * n);
    int* parents  = (int*) malloc(sizeof(int)*n);

    for (int i = 0; i < n; i++) {
      parents[i] = -1;
    }

    for (int i = 0; i < n; i++) {
      distances[i] = (i == s ? 0 : MAX);
    }

    BellmanFord(g, n,distances,parents);

    printGraph(g, n, distances, parents);

    free(g);

    return 0;
}