Dijkstra's can feel like a bit of a jump because it's not just about writing a loop; it's about managing a state. We're essentially building a map of "cheapest costs" to get from a starting point to every other node in a graph. I've seen a lot of people get bogged down in the theory, but in C, the challenge is usually just organizing your data so you don't lose your mind with pointers.

How should I represent the graph so it's actually usable?

You'll see people argue about adjacency lists versus adjacency matrices. For a small-to-medium set of nodes—say, a few cities on a map—an adjacency matrix is much easier to implement in C. It's just a 2D array where graph[i][j] is the weight of the edge between node i and node j. If there's no connection, we just put a 0 or a very large number there.

// Let's imagine 5 cities: 0: London, 1: Paris, 2: Berlin, 3: Rome, 4: Madrid
int graph[5][5] = {
    {0, 10, 0, 30, 0}, // London connections
    {10, 0, 20, 0, 0}, // Paris connections
    {0, 20, 0, 15, 0}, // Berlin connections
    {30, 0, 15, 0, 50}, // Rome connections
    {0, 0, 0, 50, 0}    // Madrid connections
};

I prefer this approach for learning because you aren't fighting with malloc and linked lists while you're trying to understand the actual algorithm. Once you've nailed the logic, you can swap the matrix for a list to save memory on sparse graphs.

How do I handle "infinity" without causing an overflow?

This is a classic C trap. Dijkstra's requires you to initialize all distances to infinity. The obvious choice is INT_MAX from limits.h, but here is the problem: the algorithm does if (dist[u] + weight < dist[v]). If dist[u] is INT_MAX, adding even a small weight will cause an integer overflow, flipping your distance to a massive negative number and breaking everything.

My advice? Use a large constant that is "big enough" but not "too big." If your maximum possible path length is 10,000, set your infinity to 1,000,000. Or, more cleanly, just check if the source node is still "infinite" before trying to relax its neighbors:

if (dist[u] == INT_MAX) continue; 
// Now it's safe to check neighbors because we know we've actually reached u

Do I really need a complex Priority Queue for this?

In a production environment with millions of nodes, yes, you'd use a Min-Heap. But for a C course or a small project, a simple linear search for the minimum distance is much more readable and perfectly fine. You just loop through your dist array, ignore the nodes you've already visited, and pick the one with the smallest current distance.

Here is how the core "relaxation" loop looks in practice:

void dijkstra(int graph[5][5], int startNode) {
    int dist[5]; 
    bool visited[5] = {false};

    for (int i = 0; i < 5; i++) dist[i] = INT_MAX;
    dist[startNode] = 0;

    for (int count = 0; count < 5 - 1; count++) {
        // Find the unvisited node with the minimum distance
        int u = -1;
        for (int i = 0; i < 5; i++) {
            if (!visited[i] && (u == -1 || dist[i] < dist[u]))
                u = i;
        }

        if (dist[u] == INT_MAX) break; // Remaining nodes are unreachable
        visited[u] = true;

        // Update distances of the neighbors of u
        for (int v = 0; v < 5; v++) {
            if (graph[u][v] != 0 && !visited[v]) {
                if (dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
}

I find that writing it this way makes the "greedy" nature of the algorithm obvious: we always take the shortest known path and see if it opens up even shorter paths to its neighbors.

📋 Practical Task

Exercise: Building a Route Finder for a Mini-Metro System

Create a C program that implements Dijkstra's algorithm to find the shortest travel time between stations in a small subway network.

The Requirements:

• Define a graph representing 6 stations (e.g., Central, North, South, East, West, Airport) using an adjacency matrix.
• Include at least 8 connections with varying travel times (weights).
• The program should allow the user to input a "Starting Station" ID and then print the minimum travel time to all other stations.
• Implement a safety check to handle "unreachable" stations (where the distance remains your chosen infinity value) by printing "Unreachable" instead of a massive integer.