Shortest paths: Dijkstra

BFS counts steps. Real routes have weights: a road takes 2 minutes or 7 minutes, a cable run costs per metre. The route with the fewest roads is not always the quickest. Dijkstra’s algorithm (1956) finds the shortest weighted path from one source to every other vertex, as long as no weight is negative.

The greedy idea

1. Give every vertex a tentative distance: 0 for the source, ∞ for the rest.
2. Pick the unfinished vertex with the smallest tentative distance. Its distance is now final.
3. For each of its neighbours, check whether going through it is shorter (“relax the edge”): if dist[u] + w < dist[v], update dist[v] and remember u as v’s predecessor.
4. Repeat until every reachable vertex is final.

Why is the smallest one safe to finalise? Any other route to it would have to leave the finished area through some vertex that is already at least as far away, and then add non-negative weights. It can only be longer or equal.

Dijkstra with PriorityQueue

Finding the smallest tentative distance is a job for a min-heap. .NET’s PriorityQueue has no “decrease priority” operation, so the standard trick is to add the vertex again with the new distance, and skip outdated entries when they come out (“lazy deletion”).

1var graph = new Dictionary<char, List<(char To, int W)>>();2void Road(char a, char b, int w)3{4    if (!graph.ContainsKey(a)) graph[a] = new();5    if (!graph.ContainsKey(b)) graph[b] = new();6    graph[a].Add((b, w));7    graph[b].Add((a, w));8}9Road('A', 'B', 4); Road('A', 'D', 2); Road('B', 'E', 3); Road('B', 'C', 6);10Road('D', 'E', 5); Road('C', 'E', 2); Road('C', 'F', 3); Road('E', 'G', 4);11Road('D', 'G', 7); Road('F', 'G', 1); Road('E', 'F', 6);12 13var (dist, prev) = Dijkstra(graph, 'A');14foreach (var place in dist.Keys.Order()) Console.Write($"{place}:{dist[place]} ");15Console.WriteLine();16 17var route = new List<char> { 'F' };18while (prev.TryGetValue(route[^1], out char p)) route.Add(p);19route.Reverse();20Console.WriteLine(string.Join(" → ", route));21 22static (Dictionary<char, int>, Dictionary<char, char>) Dijkstra(Dictionary<char, List<(char To, int W)>> g, char source)23{24    var best = new Dictionary<char, int> { [source] = 0 };25    var from = new Dictionary<char, char>();26    var pq = new PriorityQueue<char, int>();27    pq.Enqueue(source, 0);28    while (pq.TryDequeue(out char u, out int d))29    {30        if (d > best[u]) continue;                     // outdated entry: u was improved later31        foreach (var (v, w) in g[u])32        {33            int nd = d + w;34            if (nd < best.GetValueOrDefault(v, int.MaxValue))35            {36                best[v] = nd;37                from[v] = u;38                pq.Enqueue(v, nd);                     // no decrease-key: just add it again39            }40        }41    }42    return (best, from);43}

A:0 B:4 C:9 D:2 E:7 F:10 G:9 
A → D → G → F

With a binary heap the cost is O((V + E) log V). For a road network with a million junctions that is a fraction of a second. The prev map is a shortest-path tree: the best route from the source to every place at once.

Negative weights break it

Dijkstra finalises a vertex as soon as it is the closest. If some edge has a negative weight, a longer-looking route could become shorter later, after the vertex was already finalised. Example: S → A costs 2, S → B costs 5, B → A costs −4. Dijkstra finalises A at 2, but S → B → A costs 1. For negative weights, use Bellman-Ford (next lesson).

A*: Dijkstra with a sense of direction

Dijkstra spreads in all directions equally. When you only need the route to one target and can estimate the remaining distance (for example the straight-line distance on a map), A\* orders the queue by distance so far + estimate. It heads towards the target and explores far fewer vertices. As long as the estimate never overestimates, the route is still optimal. Navigation apps and game path-finding use A* and its variants.

1int[,] cost = { { 1, 3, 1, 2 }, { 1, 5, 1, 9 }, { 4, 2, 1, 1 } };2Console.WriteLine(CheapestCrossing(cost));3 4static int CheapestCrossing(int[,] cost)5{6    int rows = cost.GetLength(0), cols = cost.GetLength(1);7    var best = new int[rows, cols];8    for (int r = 0; r < rows; r++)9        for (int c = 0; c < cols; c++) best[r, c] = int.MaxValue;10    best[0, 0] = 0;11 12    var pq = new PriorityQueue<(int R, int C), int>();13    pq.Enqueue((0, 0), 0);14    (int Dr, int Dc)[] moves = { (-1, 0), (1, 0), (0, -1), (0, 1) };15    while (pq.TryDequeue(out var cell, out int d))16    {17        if (d > best[cell.R, cell.C]) continue;18        if (cell == (rows - 1, cols - 1)) return d;19        foreach (var (dr, dc) in moves)20        {21            int nr = cell.R + dr, nc = cell.C + dc;22            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;23            int nd = d + cost[nr, nc];24            if (nd < best[nr, nc]) { best[nr, nc] = nd; pq.Enqueue((nr, nc), nd); }25        }26    }27    return -1;28}

7