dijkstra.c
1/*
2 * dijkstra.c — Shortest path, adjacency list
3 * Complexity: O(V^2) — replace inner scan with
4 * min-heap for O(E log V) on sparse graphs.
5 */
6
7#include <stdio.h>
8#include <stdlib.h>
9#define INF 1e9
10
11/* Edge: chain-forward star (head[u] -> first edge of u) */
12typedef struct {
13int to, w, next;
14} Edge;
15
16/* n: vertex count (0..n-1) src: source vertex */
17/* e/head: adjlist dist[out]: shortest distance to src */
18void dijkstra(int n, int src,
19Edge *e, int *head, int *dist) {
20
21/* ── Step 1: initialize distance array ── */
22int vis[1005] = {0};
23for (int i = 0; i < n; i++)
24dist[i] = INF;
25dist[src] = 0;
26
27/* ── Step 2: greedy relaxation, V iterations ── */
28for (int k = 0; k < n; k++) {
29
30/* 2a: pick the unvisited vertex with smallest dist */
31int u = -1, min = INF;
32for (int i = 0; i < n; i++)
33if (!vis[i] && dist[i] < min)
34u = i, min = dist[i];
35
36/* no reachable vertex left — early exit */
37if (u == -1) return;
38vis[u] = 1;
39
40/* 2b: relax all outgoing edges from u */
41for (int i = head[u]; i != -1;
42i = e[i].next) {
43int v = e[i].to;
44if (dist[u] + e[i].w < dist[v])
45dist[v] = dist[u] + e[i].w;
46}
47}
48}
