modified dijkstra

gistfile1.c

#include "zombies.h"

int *dijkstra(t_graph *graph, int s) {
    // compute the safest path from starting node s to every other node
    // safest path means smallest sum of strength on vertices
    // we don't need to worry about the weight of the edges
    if(graph != NULL && graph->v > 0) {
        int p[graph->v];
        int d[graph->v];
        int paths[graph->v][graph->v];
        int v;
        int tc;
        int pos;
        t_minheap *minheap = allocate_minheap(graph->v);
        unsigned int i;
        for(i = 0; i < graph->v; i++) {
            p[i] = -1;
            d[i] = INF;
            insert(minheap, graph->vertices[i].id, INF);
        }
        // update the distance to the starting point to 0
        p[s] = 0;
        d[s] = 0;
        decrease_key(minheap, s, 0);
        pos = 0;
        while(minheap->size > 0) {
        puts("--------- DISTANCE ---------");
        for(i = 0; i < graph->v; i++)
            printf("%d | ", d[i]);
        puts("\n-------- END DISTANCE -------");

            v = (remove_min(minheap))->key;
            // the minheap is not empty
            for(i = 0; i < graph->v; i++) {
                // find neighbors to v and calculate the total cost to get to that neighbor from v
                if(graph->am[v][i] != 0 && v != i) {
                    // i is a neighbor to v
                    // what is the total cost to get to i: (d[v] + graph->am[v][i])
                    if((d[v] + graph->vertices[i].strength) < d[i]) {
                        p[i] = v;
                        d[i] = d[v] + graph->vertices[i].strength;
                        decrease_key(minheap, i, d[i]);
                    }
                }
            }
            path[pos++] = v;
        }
    }
}