#include <stdbool.h>
#include <stdlib.h>

void trace_path(unsigned int *path, unsigned int *count, unsigned int *parents, unsigned int index) {
    unsigned int parent = parents[index];
    // found root node
    if (parent == ~0) return;
    // traverse down
    trace_path(path, count, parents, parent);
    // add node into path
    path[*count] = index;
    *count += 1;
}

unsigned int min_distance(unsigned int *dist, bool *marked, unsigned int n) {
    unsigned int min_index;
    unsigned int min_dist = ~0; // max distance possible
    for (unsigned int i = 0; i < n; i += 1) if (marked[i] && dist[i] < min_dist) min_dist = dist[min_index = i];
    return min_index;
}

// find shortest path between start node and end node
// start node is not included in path
// returns amounts of node in path
unsigned int dijkstra(
    unsigned int *graph,
    unsigned int n,
    unsigned int *path,
    unsigned int start,
    unsigned int stop
) {
    bool *marked = malloc(n * sizeof * marked);
    unsigned int *dist = malloc(n * sizeof *dist); // shortest distance from start node to that node
    unsigned int *parents = malloc(n * sizeof *parents); // parent of this node
    // init data
    for (unsigned int i = 0; i < n; i++) {
        marked[i] = true;
        dist[i] = ~0; // max distance possible
        parents[i] = ~0; // root node
    }
    dist[start] = 0; // distance to itself is always 0
    // find shortest path for all node
    for (unsigned int c = 0; c < n; c += 1) {
        // pick nearest node from current data
        unsigned int u = min_distance(dist, marked, n);
        marked[u] = false;
        // update distance of adjacent node of picked node
        for (unsigned int v = 0; v < n; v += 1) {
            unsigned int ndist = dist[u] + graph[v + u * n];
            if (marked[v] && graph[v + u * n] && dist[v] > ndist) {
                parents[v] = u;
                dist[v] = ndist;
            }
        }
    }
    // traverse parents and copy to path
    unsigned int count = 0;
    trace_path(path, &count, parents, stop);
    free(parents);
    free(marked);
    free(dist);
    return count;
}