Shortest Path (Dijkstra)

Find the cheapest route from one starting node to every other node in a weighted graph.

Intuition

The big idea

Stand at the starting node. The closest neighbor is reachable in one direct hop — and you know its shortest distance is just that edge's cost. Now expand your "known" region by always grabbing the next-closest node you can reach using only known nodes. Greedy, but proven correct (as long as no negative edges).

Problem statement

Given a weighted graph G = (V, E) and a source s, find the cost of the cheapest path from s to every other vertex.

The algorithm

DIJKSTRA(graph, source):
    for each vertex v in V:
        dist[v] = ∞
    dist[source] = 0
    Settled = {}                          // nodes whose shortest dist is final

    while Settled ≠ V:
        u = vertex in V \ Settled with the smallest dist[u]
        add u to Settled
        for each edge (u, v) with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w     // "relax" the edge
                parent[v] = u
    return dist, parent

Equivalently, in the bookkeeping-table style your course uses: at each step list the edges leaving the settled set, compute min_cost(u) + cost(u,v) for each, and pick the smallest as the next settled vertex.

Interactive demo

Find shortest from 0 to 8

Worked example (from your course)

Graph with 9 nodes (0..8). Edges:

From	To	Weight
0	1	2
0	2	6
0	3	8
1	2	3
1	4	10
1	5	8
2	3	1
2	5	1
3	6	4
4	7	3
5	4	1
5	7	5
6	8	7
7	8	10

Step-by-step table

Settled set        edge       w     min_cost+w     pick
{0}                0→1        2     0+2 = 2        1   ←
                   0→2        6     0+6 = 6
                   0→3        8     0+8 = 8
─────────────────────────────────────────────────────
{0,1}              0→2        6     6
                   0→3        8     8
                   1→2        3     2+3 = 5        2   ←
                   1→4       10     2+10 = 12
                   1→5        8     2+8 = 10
─────────────────────────────────────────────────────
{0,1,2}            0→3        8     8
                   1→4       10     12
                   1→5        8     10
                   2→3        1     5+1 = 6        3   ←
                   2→5        1     5+1 = 6        5   ←
─────────────────────────────────────────────────────
{0,1,2,3,5}        1→4       10     12
                   3→6        4     6+4 = 10
                   5→4        1     6+1 = 7        4   ←
                   5→7        5     6+5 = 11
─────────────────────────────────────────────────────
{0,1,2,3,4,5}      3→6        4     10           6   ←
                   4→7        3     7+3 = 10     7   ←
                   5→7        5     11
─────────────────────────────────────────────────────
{0,1,2,3,4,5,6,7}  6→8        7     10+7 = 17    8   ←
                   7→8       10     10+10 = 20
─────────────────────────────────────────────────────
Shortest path: 0 → 1 → 2 → 3 → 6 → 8       cost = 17

Complexity

With a simple array scan to find the min each step: O(V²).
With a min-heap priority queue: O((V+E) log V).
Doesn't work with negative edge weights — for that, use Bellman-Ford.

Exam tips

What gets asked

"Find the shortest path from A to B" — make the table like above, settle vertices one at a time.
"Why is Dijkstra greedy and still correct?" — once a vertex is settled, its shortest distance can't be improved later (because all edge weights are non-negative, so any later path through unsettled vertices would only be longer).
Remember: track both dist[] and parent[] if asked to reconstruct the path.