#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <limits.h> // INT_MAX

#define INF INT_MAX

int**read_graph_file(const char*, int*);
int ** create_graph(int);
void dijkstra(int**, int, int);
int find_min_nod(int*, bool*, int);
void print_cost(int*, int, int);
void print_path(int*, int, int);
void find_path(int*,int, int);

int main()
{
    int nods, **graf, start = 1;

    graf = read_graph_file("dijkstra.in", &nods);
    dijkstra(graf, nods, start-1);

    return 0;
}

void dijkstra(int**graf, int n, int start)
{
    int *cost = (int*)malloc(sizeof(int)*n);
    int *path = (int*)malloc(sizeof(int)*n);
    bool *viz = (bool*)calloc(sizeof(int), n);
    int i, j, nod_curent;

    viz[start] = true;
    for(j = 0; j < n; j++)
    {
        cost[j] = graf[start][j];
        if(graf[start][j] != INF) path[j] = start;
    }

    for(i = 1; i < n-1; i++) // n-1 deoarece pentru ultimul nod nevizitat restul vor fi vizitate, deci nu are sens
    {
        nod_curent = find_min_nod(cost, viz, n);
        viz[nod_curent] = true;
        for(j = 0; j < n; j++)
        {
            if(viz[j] == false && graf[nod_curent][j]!= INF &&
               cost[nod_curent]+graf[nod_curent][j] < cost[j])
            {
                cost[j] = cost[nod_curent]+graf[nod_curent][j];
                path[j] = nod_curent;
            }
        }
    }

    /*print_cost(cost, n, start);
    print_path(path, n, start);*/
    FILE*out = fopen("dijkstra.out", "w+");
    for(int i = 0; i < n; i++)
        if(i != start)
            fprintf(out, "%d ", cost[i]);
    fclose(out);
    free(viz);
    free(cost);
    free(path);
}

void print_cost(int *cost, int n, int start)
{
    printf("Cost: \n");
    for(int i = 0; i < n; i++)
        if(i!=start)
            printf("(%d, %d) = %d\n", start+1, i+1, cost[i]);
    printf("\n");
}

void print_path(int *path, int n, int start)
{
    for(int i = 0; i < n; i++)
        if(i != start)
        {
            printf("%d -> %d: ", start+1, i+1);
            find_path(path,i,start);
            printf("\n");
        }
}

void find_path(int *parinte, int curent, int start)
{
    if(curent==start)
    {
        printf("%d ", curent+1);
        return;
    }
    find_path(parinte, parinte[curent], start);
    printf("%d ", curent+1);
}

int find_min_nod(int *cost, bool*viz, int n)
{
    int min_index, min_cost;
    min_cost = INF;
    for(int i = 0; i < n; i++)
        if(cost[i] < min_cost && viz[i]==false)
        {
            min_cost = cost[i];
            min_index = i;
        }

    return min_index;
}

int **read_graph_file(const char *path, int *nods)
{
    FILE *in;
    int **graf, src, dest, weight, z;

    in = fopen(path, "r+");
    if(in == NULL) { printf("Eroare la deschidere"); exit(-1); }

    fscanf(in, "%d %d", nods, &z);

    graf = create_graph(*nods);

    while(fscanf(in, "%d %d %d", &src, &dest, &weight) != EOF)
        graf[src-1][dest-1] = weight;


    fclose(in);

    return graf;
}

int **create_graph(int n)
{
    int **graf = (int**)malloc(sizeof(int*)*n);
    for(int i = 0; i < n; i++)
        graf[i] = (int*)malloc(sizeof(int)*n);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            graf[i][j] = INF;

    return graf;
}