Dijkstra's algorithm

Dijkstra's algorithm solves single-source shortest paths on a directed (or undirected) graph whose edge weights are nonnegative. It maintains tentative distances dist[v] and repeatedly settles the unsettled vertex with minimum dist, relaxing outgoing edges—similar in spirit to Prim's MST growth, but minimizing path cost instead of spanning weight. If any edge can be negative, Dijkstra is not safe; algorithms such as Bellman–Ford handle that different model.

1) Setup

• Input: graph with weight w(u,v) ≥ 0 (use ∞ or a large sentinel when no arc).
• Initialize: dist[s] = 0, all other dist[v] = ∞; mark every vertex as unsettled.
• Relax edge u → v: if dist[u] + w(u,v) < dist[v], set dist[v] to that sum (and optionally record parent[v]=u).

2) Greedy step

Among vertices not yet settled, choose u with minimum current dist[u]. Settle u and relax all arcs out of u. Correctness relies on nonnegative weights: the smallest tentative distance cannot be improved later by a path through still-unsettled vertices.

3) Example graph (directed)

Vertices 0 … 4. Source s = 0. Arcs and weights:

Directed arcs (weights):  0→1 (10),  0→2 (5),  1→3 (1),  2→1 (3),
                          2→3 (9),  2→4 (2),  3→4 (4)

Sketch:   0 --10--> 1 --1--> 3 --4--> 4
          | \              ^
          5  \_____________| (2→…)
           \___> 2 --2--> 4

4) C — Dijkstra (adjacency matrix, scan for min)

INF means “no arc” or unreachable so far. Distances use long long to reduce overflow when summing.

#include <limits.h>
#include <stdio.h>

#define V 5
#define INF LLONG_MAX / 4   /* sentinel: no arc / not reached yet */

typedef long long ll;

static ll w[V][V];       /* w[u][v] = weight of arc u→v, or INF */
static ll dist[V];       /* tentative shortest cost from source */
static int done[V];      /* 1 = settled (final dist[u]) */

static void edge(int u, int v, ll cost) {
    w[u][v] = cost;        /* directed edge */
}

/* unsettled vertex with minimum dist[]; -1 if none / all settled */
static int pick_min(void) {
    int best = -1;
    ll bestd = INF;
    for (int i = 0; i < V; i++) {
        if (done[i]) continue;
        if (dist[i] < bestd) {
            bestd = dist[i];
            best = i;
        }
    }
    return best;
}

void dijkstra(int s) {
    for (int i = 0; i < V; i++) {
        dist[i] = INF;
        done[i] = 0;
        for (int j = 0; j < V; j++)
            w[i][j] = (i == j) ? 0 : INF;   /* 0 on diagonal for relax skip */
    }
    /* sample graph from the lesson diagram */
    edge(0, 1, 10);
    edge(0, 2, 5);
    edge(1, 3, 1);
    edge(2, 1, 3);
    edge(2, 3, 9);
    edge(2, 4, 2);
    edge(3, 4, 4);

    dist[s] = 0;
    for (int it = 0; it < V; it++) {
        int u = pick_min();
        if (u < 0 || dist[u] == INF) break;   /* disconnected or done */
        done[u] = 1;   /* greedy: dist[u] is now optimal */
        for (int v = 0; v < V; v++) {
            if (u == v || w[u][v] == INF) continue;
            ll nd = dist[u] + w[u][v];   /* relax u→v */
            if (nd < dist[v]) dist[v] = nd;
        }
    }
}

int main(void) {
    dijkstra(0);   /* single-source from vertex 0 */
    for (int i = 0; i < V; i++)
        printf("dist[%d] = %lld\n", i, dist[i]);
    return 0;
}

5) Complexity

• Matrix + linear scan for the next vertex: O(V²) — simple for dense or small V (like the primers on this site).
• Adjacency list + binary min‑heap of unsettled vertices: roughly O(E log V) edge relaxations with a good decrease‑key strategy (or lazy heaps with duplicate entries).

6) Trace — source 0

∞ means “unsettled / infinite” before an update. Settled vertices are fixed for the remaining rows.

Example: shortest cost to vertex 4 is 7 via 0 → 2 → 4 (cost 5 + 2).