Structs & Data Structures · intermediate · ~14 min

Dijkstra's shortest path

Weighted shortest paths with non-negative edges.

Overview

When edges have positive weights, the fewest-edges path is no longer the cheapest path. Dijkstra's algorithm finds true shortest distances: it keeps a tentative distance to every vertex, repeatedly finalises the closest unfinished one, and relaxes its outgoing edges (dist[v] = min(dist[v], dist[u]+weight)). On a dense adjacency matrix the plain O(n²) selection version is the natural fit.

Why it matters

Dijkstra is the shortest-path workhorse: GPS routing, network packet routing, least-cost pathfinding in games, and any 'cheapest way from A to B' with non-negative costs. The same single run yields a vertex's eccentricity — its distance to the farthest reachable vertex.

Core concepts

Tentative distances. Start at ∞ for all but the source (0).

Greedy finalisation. The nearest unfinished vertex can be locked in — no later path can beat it when weights are non-negative.

Relaxation. For each edge u→v with weight w>0, improve dist[v] to dist[u]+w if smaller.

Non-negative requirement. Negative edges break the greedy choice (use Bellman-Ford there).

Why the greedy choice is safe. When the nearest unfinished vertex is selected, any alternative route to it would have to leave through some other unfinished vertex whose tentative distance is already larger — and with non-negative weights a longer prefix can never produce a shorter total. That argument fails the moment an edge can be negative, which is precisely why Dijkstra requires non-negative weights.

Syntax notes

#include <stdlib.h>

/* w[i*n+j] > 0 is an edge weight; 0 means NO EDGE (not a zero-cost edge) */
long dijkstra(const int *w, int n, int src, int dst) {
    const long INF = 1000000000L;
    long *dist = malloc((size_t)n * sizeof *dist);
    int  *done = calloc((size_t)n, sizeof *done);
    if (!dist || !done) { free(dist); free(done); return -1; }
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[src] = 0;
    for (int it = 0; it < n; it++) {
        int u = -1; long best = INF;
        for (int i = 0; i < n; i++)                 /* pick the nearest unfinished vertex */
            if (!done[i] && dist[i] < best) { best = dist[i]; u = i; }
        if (u < 0) break;                           /* everything remaining is unreachable */
        done[u] = 1;
        for (int v = 0; v < n; v++) {               /* relax its outgoing edges */
            int e = w[u*n + v];
            if (e > 0 && dist[u] + e < dist[v]) dist[v] = dist[u] + e;
        }
    }
    long r = dist[dst];
    free(dist); free(done);
    return (r >= INF) ? -1 : r;
}

Key points:

e > 0 is the edge test; treating 0 as a zero-cost edge would connect everything.
Once a vertex is done, its distance is final — that is the greedy invariant.
Requires non-negative weights; negative edges break the invariant (use Bellman-Ford).

Lesson

When edges carry positive weights, BFS no longer gives shortest paths — Dijkstra's algorithm does. It keeps tentative distances, repeatedly finalises the closest unfinished vertex, and relaxes its outgoing edges. On a dense adjacency matrix the simple O(n²) selection form is ideal. The eccentricity of a vertex — its farthest shortest distance — falls out of one run.

Code examples

#include <stdio.h> int main(void){ int n=4; /* weighted; 0 = no edge */ int w[16]={ 0,4,1,0, 0,0,0,5, 0,2,0,1, 0,0,0,0 }; long INF=1000000000L, dist[4]; int done[4]={0}, src=0; for(int i=0;i<n;i++) dist[i]=INF; dist[src]=0; for(int it=0;it<n;it++){ int u=-1; long best=INF; for(int i=0;i<n;i++) if(!done[i]&&dist[i]<best){best=dist[i];u=i;} if(u<0)break; done[u]=1; for(int v=0;v<n;v++){ int e=w[u*n+v]; if(e>0&&dist[u]+e<dist[v]) dist[v]=dist[u]+e; } } for(int i=0;i<n;i++) printf("shortest %d -> %d = %ld\n", src, i, dist[i]); return 0; }

Line by line

Step	Line	What happens
1	`dist[src] = 0`, rest INF	Only the source has a known distance to begin with.
2	selection loop	Picks the unfinished vertex with the smallest tentative distance — initially the source.
3	`done[u] = 1`	Locks in `dist[u]`. With non-negative weights no later path can improve it.
4	relaxation	For each edge `u->v`, if going via `u` is cheaper, `dist[v]` is lowered.
5	`u < 0`	No reachable unfinished vertex remains; the rest of the graph is unreachable, so stop early.
6	result	`dist[dst]`, or -1 if it is still INF. In the demo graph 0->3 costs 2 via vertex 2, beating the direct route.

Common mistakes

Treating a 0 weight as a real zero-cost edge instead of 'no edge'. Using BFS and ignoring weights. Applying Dijkstra with negative weights. Letting ∞ (unreachable) leak into an eccentricity maximum.

Debugging tips

Compiler errors and warnings:

-Wsign-compare mixing int weights with long distances; keep the accumulator wide and explicit.
No warning for using it with negative weights.

Runtime symptoms:

Every vertex appears reachable at distance 0. You treated w == 0 as a zero-cost edge. Only > 0 is an edge in this representation.
Distances are wrong with negative weights. Dijkstra's greedy lock-in is invalid there — that is Bellman-Ford's job, not a bug in your code.
Unreachable vertices report a huge number. You returned dist[dst] without translating INF back to -1.
INF + weight overflows into a small number. Guard the relaxation (dist[u] != INF) or pick an INF small enough that INF + max_weight still fits.
Infinite loop or wrong picks. You forgot done[u] = 1, so the same vertex is selected repeatedly.

Technique: verify against BFS on a graph where every weight is 1 — Dijkstra must produce identical distances. Any disagreement isolates the bug quickly.

Memory safety

Sentinel arithmetic. dist[u] + e with dist[u] == INF can overflow if INF is near the type's maximum. Either guard with dist[u] != INF or choose INF as a large-but-safe constant (as above), leaving headroom for the largest edge weight.
Two allocations, one failure path. Check both; free whatever succeeded before returning.
done must be zeroed (calloc); garbage marks vertices as finished and truncates the search.
Validate src and dst before indexing.
Weight semantics are an unchecked contract. "0 means no edge" must be documented, since a caller who intends a zero-cost edge will get silently wrong results.
Complexity. This dense O(n^2) form is right for a matrix; a priority-queue version is O((V+E) log V) and better for sparse graphs — but do not mix the two representations' assumptions.

Real-world uses

Concrete uses: GPS and mapping route computation, network routing protocols (OSPF uses a Dijkstra-based shortest-path-first calculation), least-cost pathfinding in games, flight and fare search, and any "cheapest route" query over non-negative costs. Eccentricity — the farthest shortest distance from a vertex — feeds into centrality measures used in network analysis.

Professional best practices:

Beginner:

Treat only positive entries as edges, and say so in a comment.
Translate INF back into a meaningful "unreachable" value at the API boundary.

Intermediate:

Use a binary heap for sparse graphs; keep the O(n^2) selection loop for dense matrices where it is actually competitive.
If any weight can be negative, switch to Bellman-Ford and detect negative cycles explicitly.
Keep a parent[] array if the caller needs the route, not just its cost — recomputing it afterwards is wasteful.

Practice tasks

1. (Beginner) Shortest distance. Implement dijkstra(w, n, src, dst) returning -1 when unreachable and 0 for src == dst. Concepts: relaxation, INF sentinel.

2. (Beginner) Cross-check with BFS. Build a graph where every weight is 1 and confirm Dijkstra's distances match BFS hop counts. Concepts: validating against a simpler oracle.

3. (Intermediate) Eccentricity. Implement dijkstra_eccentricity(w, n, src) — the largest finite distance from src. Requirements: unreachable vertices must not count. Concepts: reusing one run.

4. (Intermediate) Reconstruct the route. Add a parent[] array and print the actual cheapest path. Concepts: path reconstruction.

Summary

When edges carry positive weights, fewest-hops is no longer cheapest, and Dijkstra's algorithm finds true shortest distances: keep tentative distances, repeatedly finalise the nearest unfinished vertex, and relax its outgoing edges. Finalising is safe only because weights are non-negative — with a negative edge the greedy lock-in is invalid and you need Bellman-Ford. In this matrix representation a weight of 0 means no edge, not a zero-cost one, so the relaxation must test w > 0; and the INF sentinel needs enough headroom that INF + weight cannot overflow. Translate INF back to a clear "unreachable" value at the boundary, and keep a parent array if the caller needs the route rather than just its cost.