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

#define inf 999

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;

// clang-format off
int tempMatrix[][10] = {{0, 1, inf, inf, inf, inf, inf, inf, inf, 20},
                        {1, 0, inf, 1, 2, inf, inf, inf, inf, inf},
                        {inf, inf, 0, 1, 1, 1, inf, inf, inf, inf},
                        {inf, 1, 1, 0, 3, inf, inf, inf, inf, inf},
                        {inf, 2, 1, 3, 0, inf, inf, inf, inf, inf},
                        {inf, inf, 1, inf, inf, 0, inf, 1, inf, inf},
                        {inf, inf, inf, inf, inf, inf, 0, inf, inf, inf},
                        {inf, inf, inf, inf, inf, 1, inf, 0, 1, 1},
                        {inf, inf, inf, inf, inf, inf, inf, 1, 0, 1},
                        {20, inf, inf, inf, inf, inf, inf, 1, 1, 0}};
// clang-format on

graphMatrix initGraphMatrix()
{
	graphMatrix graph;
	graph.numNodes = 10;
	graph.costMatrix = (int**)malloc(sizeof(int*) * graph.numNodes);
	for (int i = 0; i < graph.numNodes; i++) {
		graph.costMatrix[i] = (int*)malloc(sizeof(int) * graph.numNodes);
		for (int j = 0; j < graph.numNodes; j++)
			graph.costMatrix[i][j] = tempMatrix[i][j];
	}
	return graph;
}

typedef struct nodeDP {
	int node;
	int d;
	int parent;
} nodeDP;

int getMinimum(int v[], nodeDP* NDP, int n)
{
	int minDist = inf;
	int minNode = 0;

	for (int i = 0; i < n; i++) {
		if (!v[i] && NDP[i].d < minDist) {
			minDist = NDP[i].d;
			minNode = i;
		}
	}

	return minNode;
}

int cmpNDP(const void* a, const void* b)
{
	nodeDP* A = (nodeDP*)a;
	nodeDP* B = (nodeDP*)b;
	return (A->d - B->d);
}

void printNDP(nodeDP* NDP, int n)
{
	printf("  Node: ");
	for (int i = 0; i < n; i++)
		printf("%5i", NDP[i].node);
	printf("\n");
	printf("     D: ");
	for (int i = 0; i < n; i++)
		printf("%5i", NDP[i].d);
	printf("\n");
	printf("Parent: ");
	for (int i = 0; i < n; i++)
		printf("%5i", NDP[i].parent);
	printf("\n");
}

nodeDP* dijsktra(graphMatrix graph, int source)
{
	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * graph.numNodes);
	if (NDP == NULL)
		return NULL;
	for (int i = 0; i < graph.numNodes; i++) {
		NDP[i].node = i;
		NDP[i].d = inf;
		NDP[i].parent = -1;
	}
	NDP[source].d = 0;
	// TODO

	int* visited = (int*)malloc(graph.numNodes * sizeof(int));
	for (int i = 0; i < graph.numNodes; i++) {
		visited[i] = 0;
	}

	int numVisited = 0;
	int current = source;

	while (numVisited != graph.numNodes) {
		for (int i = 0; i < graph.numNodes; i++) {
			if (graph.costMatrix[current][i] != inf && i != current && !visited[i]) {
				if (NDP[i].d > NDP[current].d + graph.costMatrix[current][i]) {
					NDP[i].d = NDP[current].d + graph.costMatrix[current][i];
					NDP[i].parent = current;
				}
			}
		}
		visited[current] = 1;
		numVisited++;
		current = getMinimum(visited, NDP, graph.numNodes);
	}
	qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);

	return NDP;
}

int main()
{
	graphMatrix graphM = initGraphMatrix();
	printf("\n");

	nodeDP* NDP = dijsktra(graphM, 0);
	printf("\nDijsktra rezult:\n");
	printNDP(NDP, graphM.numNodes);

	return 0;
}