data-structures · advanced · ~50 min
Greedy relaxation with a priority structure; non-negative-weight shortest paths.
Given a graph with N <= 32 vertices encoded as an adjacency matrix int w[N][N] (w[i][j] = edge weight from i to j, or 0 if no edge; weights are positive), and a source s, compute int dist[N] so that dist[i] is the shortest distance from s to i. If unreachable, dist[i] = -1.
Implement void dijkstra(int n, int w[][32], int s, int *dist).
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.
n vertices, weight matrix, source.
dist array of length n.
n <= 32. No negative weights. Use a simple linear extract-min (no heap required).
void dijkstra(int n, int w[][32], int s, int *dist) { /* TODO */ }
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.
Disconnected vertices remain -1. Source has dist 0.
O(n^2) with linear extract-min. With a binary heap, O((n+m) log n).
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.