/* Dijkstra's algorithm: find shortest path from s to t */
void dijkstra(graph_t *g, node_t s, node_t t)
{
    node_t n;
    link_t e;
    heap_t *h;

    h = heap_new(g->nnodes, (generic_t) (void *) g, shorter, update);

    /* Initialize node distances and insert into heap. */
    graph_advise_seq(g);
    for_each_node(g, n) {
        PRED(g,n) = NONE;
        DIST(g,n) = (n == s) ? 0 : INF;
        heap_insert(h, (generic_t) n);
    }

    /* Iteratively pick node with shortest distance from heap. */
    graph_advise_rnd(g);
    while (!heap_is_empty(h)) {
        n = (node_t) heap_remove(h).u;
        if (n == t)
            /* Destination reached. */
            break;
        /* Explore neighbors. */
        for_each_out_link(g, n, e) {
            node_t m = HEAD(g,e);
            int newdist = DIST(g,n) + 1;
            if (newdist < DIST(g,m)) {
                /* Improve distance. */
                DIST(g,m) = newdist;
                PRED(g,m) = n;
                /* Restore heap property. */
                heap_fix_up(h, HEAPIND(g,m));
            }
        }
    }

    heap_free(h);
}