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)
}

Let's trace through what happens when we call dijkstra(*g, 0):

• Start: dist = [0, INF, INF, INF]. Push (node=0, dist=0) onto the heap.
• Pop (0, 0). Mark node 0 visited. Relax edges: dist[1] = 2, dist[2] = 6. Push both.
• Pop (1, 2). Mark node 1 visited. Relax: dist[2] = min(6, 2+1) = 3. dist[3] = 5. Push updated entries.
• Pop (2, 3). Mark node 2 visited. Relax: dist[3] = min(5, 3+1) = 4. Push (3, 4).
• Pop (3, 4). Mark node 3 visited. No outgoing edges. Done.
• Final distances: [0, 2, 3, 4].

Graph Coloring Algorithm (Adjacency List)

Graph coloring assigns colors to each vertex in a graph such that no two adjacent vertices share the same color. This has practical applications in compiler register allocation, scheduling problems, and map coloring. This implementation uses a greedy graph coloring algorithm with an adjacency list represented as a dynamic array of dynamic arrays. Each vertex has a list of neighbors it is connected to.

#import "Basic";

// The graph is represented as an adjacency list.
// adjacency_list[i] is a dynamic array of ints listing
// all vertices that vertex i is connected to.
Graph :: struct {
    num_vertices    : int;
    adjacency_list  : [..] [..] int;  // array of dynamic arrays
}

// Add an undirected edge between vertex u and vertex v.
add_edge :: (g: *Graph, u: int, v: int) {
    array_add(*g.adjacency_list[u], v);
    array_add(*g.adjacency_list[v], u);
}

// Initialize a graph with a given number of vertices.
make_graph :: (num_vertices: int) -> Graph {
    g : Graph;
    g.num_vertices = num_vertices;

    // Reserve one neighbor-list slot per vertex
    for i: 0..num_vertices - 1 {
        neighbor_list : [..] int;
        array_add(*g.adjacency_list, neighbor_list);
    }
    return g;
}

// Greedy graph coloring algorithm.
// Returns a dynamic array where result[i] is the color assigned to vertex i.
// Colors are integers starting from 0.
graph_color :: (g: *Graph) -> [..] int {
    num_vertices := g.num_vertices;

    // Initialize every vertex's color to -1 (uncolored)
    colors : [..] int;
    for i: 0..num_vertices - 1 {
        array_add(*colors, -1);
    }

    // Color the first vertex with color 0
    colors[0] = 0;

    // Assign colors to the remaining vertices one by one
    for vertex: 1..num_vertices - 1 {

        // Track which colors are already used by this vertex's neighbors.
        // neighbor_has_color[c] = true means a neighbor is using color c.
        neighbor_has_color : [..] bool;
        for c: 0..num_vertices - 1 {
            array_add(*neighbor_has_color, false);
        }

        // Mark colors used by all neighbors of this vertex
        for neighbor: g.adjacency_list[vertex] {
            neighbor_color := colors[neighbor];
            if neighbor_color != -1 {
                neighbor_has_color[neighbor_color] = true;
            }
        }

        // Assign the smallest color not used by any neighbor
        chosen_color := 0;
        while chosen_color < num_vertices && neighbor_has_color[chosen_color] {
            chosen_color += 1;
        }
        colors[vertex] = chosen_color;

        array_free(neighbor_has_color);
    }

    return colors;
}

// Print the graph's adjacency list for debugging
print_graph :: (g: *Graph) {
    print("Graph adjacency list:\n");
    for vertex: 0..g.num_vertices - 1 {
        print("  Vertex %: ", vertex);
        for neighbor: g.adjacency_list[vertex] {
            print("% ", neighbor);
        }
        print("\n");
    }
}

// Print the coloring result
print_coloring :: (colors: [..] int) {
    print("Vertex coloring:\n");
    for color, vertex: colors {
        print("  Vertex % -> Color %\n", vertex, color);
    }
}

// Count the total number of distinct colors used
count_colors :: (colors: [..] int) -> int {
    max_color := -1;
    for color: colors {
        if color > max_color  max_color = color;
    }
    return max_color + 1;
}

main :: () {
    // Build a simple example graph:
    //
    //   0 --- 1
    //   |   / |
    //   |  /  |
    //   | /   |
    //   2 --- 3
    //
    // This is a cycle of 4 nodes with a diagonal (0-1-2-3-0 + edge 1-2).
    // It requires 3 colors because of the triangle formed by 0, 1, 2.

    g := make_graph(4);
    add_edge(*g, 0, 1);
    add_edge(*g, 0, 2);
    add_edge(*g, 1, 2);
    add_edge(*g, 1, 3);
    add_edge(*g, 2, 3);

    print_graph(*g);
    print("\n");

    colors := graph_color(*g);
    print_coloring(colors);

    total := count_colors(colors);
    print("\nTotal colors used: %\n", total);

    // Clean up
    array_free(colors);
    for i: 0..g.num_vertices - 1 {
        array_free(g.adjacency_list[i]);
    }
    array_free(g.adjacency_list);
}

Expected Output

Graph adjacency list:
  Vertex 0: 1 2
  Vertex 1: 0 2 3
  Vertex 2: 0 1 3
  Vertex 3: 1 2

Vertex coloring:
  Vertex 0 -> Color 0
  Vertex 1 -> Color 1
  Vertex 2 -> Color 2
  Vertex 3 -> Color 0

Total colors used: 3

Expected Output Explained

The greedy algorithm works through the vertices in order (0, 1, 2, ...):

• Vertex 0 gets Color 0 (it's first, nothing to conflict with).
• Vertex 1 is adjacent to 0 (Color 0), so it gets Color 1.
• Vertex 2 is adjacent to 0 (Color 0) and 1 (Color 1), so it gets Color 2.
• Vertex 3 is adjacent to 1 (Color 1) and 2 (Color 2). Color 0 is free, so it gets Color 0.

Note that greedy coloring does not guarantee the globally minimum number of colors (the chromatic number). The result can depend on vertex ordering. For optimal coloring, you'd need a more complex backtracking algorithm, but greedy is fast and works well in practice.

Notes on this Code

• Graph :: struct { ... } — defining a named struct as a constant
• [..] [..] int — a dynamic array of dynamic arrays (the adjacency list)
• array_add(*g.adjacency_list, neighbor_list) — adding to a dynamic array via pointer
• for neighbor: g.adjacency_list[vertex] — iterating directly over a dynamic array
• array_free(...) — explicit memory cleanup (no garbage collector!)
• g.num_vertices - 1 used in for vertex: 1..num_vertices - 1 — ranges are inclusive on both ends
• defer could be used here to ensure array_free is called, but was kept explicit for clarity