Dijkstra shortest paths (small graph)

Challenge

Compute single-source shortest path distances with Dijkstra's algorithm.

Task

Implement void dijkstra(int n, int w[][32], int s, int *dist). The graph has n vertices encoded as an adjacency matrix w, where w[i][j] is the positive weight of the edge from i to j, or 0 if there is no edge. Fill dist[i] with the shortest distance from source s to vertex i; use -1 for vertices that are unreachable.

Input

• n: number of vertices (n <= 32).
• w: an adjacency matrix declared int w[][32]; w[i][j] > 0 is an edge weight, w[i][j] == 0 means no edge.
• s: the source vertex.
• dist: a writable array of at least n ints to fill with results.

Output

Nothing returned; dist[i] is the shortest distance from s to i, or -1 if i is unreachable. dist[s] is 0.

Example

edges: 0-1 (1), 1-2 (2), 0-2 (4), source 0
dist  ->   {0, 1, 3}    (0->1->2 costs 3, cheaper than the direct edge of 4)
disconnected vertex      ->   -1

Edge cases

• The source has distance 0.
• Vertices with no path from s remain -1.

Rules

• All weights are positive (no negative edges). A simple linear scan to find the next-closest vertex is fine; no heap is required.

Why this matters

Dijkstra's algorithm powers GPS routing, internet packet routing (OSPF), and every shortest-path query you can imagine. Implementing it from scratch is a rite of passage.

Input format

n (<= 32); w: int w[][32] adjacency matrix (0 = no edge, positive = weight); source s; dist: array of >= n ints.

Output format

Nothing returned; dist[i] is the shortest distance from s to i, or -1 if unreachable.

Constraints

n <= 32. No negative weights. Use a simple linear extract-min (no heap required).

Starter code

void dijkstra(int n, int w[][32], int s, int *dist) { /* TODO */ }

Common mistakes

Forgetting to initialize dist to a sentinel; processing the same vertex twice; treating w[i][j]==0 as a zero-weight edge instead of absence.

Edge cases to handle

Disconnected vertices remain -1. Source has dist 0.

Complexity

O(n^2) with linear extract-min. With a binary heap, O((n+m) log n).

Background lessons

• Binary trees
• Hash tables