Graph Algorithms

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph where all edge weights are non-negative. It works by maintaining a priority queue of nodes to visit, always processing the node with the smallest known distance first. The time complexity is O((V + E) log V) with a binary heap priority queue, where V is the number of vertices and E is the number of edges.

Graph Representation

We represent the graph as an adjacency list: each node stores a dynamic array of its neighbors and the weights of the edges connecting them. This is memory-efficient for sparse graphs and fast for iterating neighbors.

// An edge connects 'to' with a given 'weight'
Edge :: struct {
    to:     int;
    weight: int;
}

// A node holds all its outgoing edges
Node :: struct {
    edges: [..] Edge;
}

// The graph is just an array of nodes
Graph :: struct {
    nodes: [..] Node;
}

// Create a graph with 'num_nodes' nodes
graph_create :: (num_nodes: int) -> Graph {
    g: Graph;
    for 0..num_nodes - 1 {
        node: Node;
        array_add(*g.nodes, node);
    }
    return g;
}

// Add a directed edge from 'from' to 'to' with the given weight
graph_add_edge :: (g: *Graph, from: int, to: int, weight: int) {
    edge := Edge.{to = to, weight = weight};
    array_add(*g.nodes[from].edges, edge);
}

Priority Queue

Dijkstra's algorithm needs a priority queue to efficiently retrieve the unvisited node with the smallest tentative distance. We implement a simple min-heap using a dynamic array.

// An entry in the priority queue: which node and its current best distance
PQ_Entry :: struct {
    node:     int;
    distance: int;
}

// Priority queue (min-heap) — smallest distance at index 0
PQ :: struct {
    data: [..] PQ_Entry;
}

// Swap two entries
pq_swap :: (pq: *PQ, a: int, b: int) {
    pq.data[a], pq.data[b] = pq.data[b], pq.data[a];
}

// Sift an entry up to restore heap order
pq_sift_up :: (pq: *PQ, i: int) {
    while i > 0 {
        parent := (i - 1) / 2;
        if pq.data[i].distance < pq.data[parent].distance {
            pq_swap(pq, i, parent);
            i = parent;
        } else {
            break;
        }
    }
}

// Sift an entry down to restore heap order
pq_sift_down :: (pq: *PQ, i: int) {
    n := pq.data.count;
    while true {
        smallest := i;
        left  := 2 * i + 1;
        right := 2 * i + 2;

        if left < n && pq.data[left].distance < pq.data[smallest].distance {
            smallest = left;
        }
        if right < n && pq.data[right].distance < pq.data[smallest].distance {
            smallest = right;
        }
        if smallest == i  break;

        pq_swap(pq, i, smallest);
        i = smallest;
    }
}

// Push a new entry onto the heap
pq_push :: (pq: *PQ, node: int, dist: int) {
    array_add(*pq.data, .{node = node, distance = dist});
    pq_sift_up(pq, pq.data.count - 1);
}

// Pop the minimum-distance entry off the heap
pq_pop :: (pq: *PQ) -> PQ_Entry {
    top := pq.data[0];
    last := pq.data.count - 1;
    pq.data[0] = pq.data[last];
    pq.data.count -= 1;  // shrink without freeing memory
    if pq.data.count > 0  pq_sift_down(pq, 0);
    return top;
}

Dijkstra Procedure Implementation

This function returns the array of shortest distances from 'start' to every node. Unreachable nodes have distance S64_MAX (treated as infinity).

dijkstra :: (g: *Graph, start: int) -> [] int {

    INF :: 0x7FFF_FFFF;   // large sentinel value for "infinity"
    n := g.nodes.count;

    // dist[i] = best known distance from start to node i
    dist := NewArray(n, int);
    for i : 0..n - 1  dist[i] = INF;
    dist[start] = 0;

    // visited[i] = true once node i's shortest distance is finalised
    visited := NewArray(n, bool);
    for i : 0..n - 1  visited[i] = false;

    // Initialise the priority queue with the starting node
    pq: PQ;
    pq_push(*pq, start, 0);

    while pq.data.count > 0 {
        // Always process the node with the smallest current distance
        entry := pq_pop(*pq);
        u := entry.node;

        // Skip if we already found the best path to u
        if visited[u]  continue;
        visited[u] = true;

        // Relax all outgoing edges from u
        for edge : g.nodes[u].edges {
            v := edge.to;
            new_dist := dist[u] + edge.weight;

            if new_dist < dist[v] {
                dist[v] = new_dist;
                pq_push(*pq, v, new_dist);
            }
        }
    }

    return dist;
}

Example Usage

Below is a complete main() that builds a small weighted graph, runs Dijkstra from node 0, and prints the results.

main :: () {

    //  Graph layout:
    //
    //       2       3
    //  0 -------> 1 -------> 3
    //  |          |          ^
    //  |  6       | 1        | 1
    //  +------->  2 ---------+

    g := graph_create(4);  // 4 nodes: 0, 1, 2, 3

    graph_add_edge(*g, 0, 1, 2);  // 0 -> 1, cost 2
    graph_add_edge(*g, 0, 2, 6);  // 0 -> 2, cost 6
    graph_add_edge(*g, 1, 2, 1);  // 1 -> 2, cost 1
    graph_add_edge(*g, 1, 3, 3);  // 1 -> 3, cost 3
    graph_add_edge(*g, 2, 3, 1);  // 2 -> 3, cost 1

    dist := dijkstra(*g, 0);

    print("Shortest distances from node 0:\n");
    for i : 0..dist.count - 1 {
        print("  Node % -> %\n", i, dist[i]);
    }
    // Expected output:
    //   Node 0 -> 0
    //   Node 1 -> 2
    //   Node 2 -> 3   (via 0->1->2, cost 2+1=3, not 0->2 cost 6)
    //   Node 3 -> 4   (via 0->1->2->3, cost 2+1+1=4)
}