Shortest Paths: Dijkstra, PriorityQueue and a Brief Look at A*

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

The Bookstore shipping network: lines between cities, each with a shipping cost (unit cost, example values). Which route is cheapest from the warehouse in Istanbul to a customer in Antalya?

WeightedGraph g = new();
g.AddEdge("Istanbul", "Bursa", 4);
g.AddEdge("Istanbul", "Eskisehir", 9);
g.AddEdge("Bursa", "Eskisehir", 4);
g.AddEdge("Bursa", "Izmir", 8);
g.AddEdge("Eskisehir", "Ankara", 6);
g.AddEdge("Eskisehir", "Izmir", 11);
g.AddEdge("Ankara", "Konya", 7);
g.AddEdge("Konya", "Antalya", 8);
g.AddEdge("Izmir", "Antalya", 12);

Roughly, the routes fall into two groups: north via Ankara and Konya, or west via Izmir. Which is cheaper, and by how many units? Add it up in your head and keep your guess. Also think about this: can the BFS (Breadth-First Search) from the 15th post of the series answer this question correctly?

Why BFS Is Not Enough

BFS assumes all edges are equal: a step is a step. This network has two three-line routes: Istanbul, Bursa, Izmir, Antalya (4 + 8 + 12 = 24) and Istanbul, Eskisehir, Izmir, Antalya (9 + 11 + 12 = 32). For BFS both have the same length; which one it returns depends only on the order the edges were added to the graph. With this insertion order we are lucky; add Istanbul's lines in reverse order and BFS returns the 32-unit route as "the shortest". On top of that, in a weighted graph four cheap lines can cost less than three expensive ones. We need an algorithm that advances in order of "lowest total cost" instead of "fewest steps".

If all weights are equal (or all 1), BFS is still correct and the fastest option. If weights are only 0 and 1, 0-1 BFS with a deque is enough. For general non-negative weights the standard answer is Dijkstra.

Writing Dijkstra with PriorityQueue

The algorithm Edsger Dijkstra published in 1959 replaces BFS's queue with a priority queue: it always processes the city with the cheapest distance known so far. Without negative weights, the distance of a city leaving the priority queue is final; any path found later passes through an already more expensive point and cannot make it cheaper.

public sealed record PathResult(int Cost, IReadOnlyList<string> Path);

// Dijkstra with PriorityQueue and lazy deletion. O((V + E) log V); weights must be >= 0.
public static PathResult? Dijkstra(WeightedGraph graph, string source, string target, Action<string, int>? onSettled = null)
{
    Dictionary<string, int> dist = new() { [source] = 0 };
    Dictionary<string, string> previous = [];
    PriorityQueue<string, int> queue = new();
    queue.Enqueue(source, 0);

    while (queue.TryDequeue(out string? city, out int d))
    {
        if (d > dist[city])
        {
            continue; // stale entry: a shorter path was found after it was queued
        }

        onSettled?.Invoke(city, d);
        if (city == target)
        {
            return new PathResult(d, BuildPath(previous, target));
        }

        foreach ((string next, int cost) in graph.Edges(city))
        {
            int candidate = d + cost;
            if (candidate < dist.GetValueOrDefault(next, int.MaxValue))
            {
                dist[next] = candidate;
                previous[next] = city;
                queue.Enqueue(next, candidate); // no decrease-key: enqueue a new entry
            }
        }
    }

    return null;
}

Two lines of the loop are the real subject of this post. We saw it in the 13th post of the series: .NET's PriorityQueue has no decrease-key. When we find a cheaper path to a city we cannot lower the priority of the old entry in the queue. Instead we add the city once more with the new cost. The old entry stays in the queue and comes out some day; when it does, the d > dist[city] check recognizes it as stale and skips it. This is called lazy deletion. The price is that the queue can grow to as many as E entries; but log E and log V differ only by a constant factor (since E is at most V², log E ≤ 2 log V), so the cost stays O((V + E) log V).

Step by Step: What Happens in the Queue

Here is what happens on the way from Istanbul to Antalya, from a copy of the same algorithm that prints every queue event:

  pop Istanbul 0: Bursa=4, Eskisehir=9
  pop Bursa 4: Eskisehir=8, Izmir=12
  pop Eskisehir 8: Ankara=14
  pop Eskisehir 9: stale, skip
  pop Izmir 12: Antalya=24
  pop Ankara 14: Konya=21
  pop Konya 21:
  pop Antalya 24: 

The answer to the opening question: the cheapest route is the western one via Izmir at 24 units; the northern route (Bursa, Eskisehir, Ankara, Konya) is 4 + 4 + 6 + 7 + 8 = 29. For path reconstruction we keep, for every city, the city we came from in previous and walk back from the target:

private static List<string> BuildPath(Dictionary<string, string> previous, string target)
{
    List<string> path = [target];
    while (previous.TryGetValue(path[^1], out string? p)) path.Add(p);
    path.Reverse();
    return path;
}

settled Istanbul     0
settled Bursa        4
settled Eskisehir    8
settled Izmir       12
settled Ankara      14
settled Konya       21
settled Antalya     24
cost=24 path=Istanbul -> Bursa -> Izmir -> Antalya

Two details. We stop the moment the target is dequeued, not when we first find 24 for Antalya (step 5), because at that point a cheaper path could still have been possible. And since stale entries are skipped, previous always holds the latest and best update; Eskisehir's parent is Bursa, not Istanbul.

Negative Weights: Where Dijkstra Breaks

Dijkstra's "whatever is dequeued is final" assumption collapses with a negative edge. Let's add a campaign to the shipping network: for empty return trucks from Izmir to Bursa, the carrier refunds 4 units:

WeightedGraph refund = new();
refund.AddEdge("Depot", "Bursa", 2, bidirectional: false);
refund.AddEdge("Depot", "Izmir", 5, bidirectional: false);
refund.AddEdge("Izmir", "Bursa", -4, bidirectional: false);
Console.WriteLine($"Dijkstra Depot->Bursa: {ShortestPath.Dijkstra(refund, "Depot", "Bursa")!.Cost}");
Console.WriteLine($"Bellman-Ford Depot->Bursa: {ShortestPath.BellmanFord(refund, "Depot")!["Bursa"]}");

Dijkstra Depot->Bursa: 2
Bellman-Ford Depot->Bursa: 1

Dijkstra dequeues Bursa at cost 2, considers it final and stops; yet the route Depot, Izmir, Bursa costs 5 - 4 = 1. With negative weights you need Bellman-Ford: it relaxes all edges for V - 1 rounds, and if there is still an improvement in a V-th round, it reports a negative cycle:

// Bellman-Ford: O(V * E), handles negative weights, detects negative cycles.
public static Dictionary<string, int>? BellmanFord(WeightedGraph graph, string source)
{
    List<string> vertices = [.. graph.Vertices];
    Dictionary<string, int> dist = vertices.ToDictionary(v => v, _ => int.MaxValue);
    dist[source] = 0;
    for (int round = 0; round < vertices.Count - 1; round++)
    {
        bool changed = false;
        foreach (string u in vertices)
        {
            if (dist[u] == int.MaxValue) continue;
            foreach ((string v, int cost) in graph.Edges(u))
            {
                if (dist[u] + cost < dist[v])
                {
                    dist[v] = dist[u] + cost;
                    changed = true;
                }
            }
        }

        if (!changed) break;
    }

    foreach (string u in vertices)
    {
        if (dist[u] == int.MaxValue) continue;
        foreach ((string v, int cost) in graph.Edges(u))
        {
            if (dist[u] + cost < dist[v]) return null; // negative cycle
        }
    }

    return dist;
}

With a negative cycle the "shortest path" is undefined: going around the cycle lowers the cost forever. In real life this is usually a data error (two lines' refunds feeding each other) or something deliberately searched for, like currency arbitrage. The O(V·E) cost is much higher than Dijkstra's; so if you know weights are non-negative use Dijkstra, and if you are not sure, validate the data first.

A*: Looking Toward the Goal

Dijkstra does not know where the target is; it spreads from the start at the same speed in every direction. Picture a robot in the warehouse going from the top-left corner to the bottom-right between shelves: Dijkstra explores the aisles behind the robot with the same priority as those close to the goal. A* (Hart, Nilsson and Raphael, 1968) makes the queue priority g + h: g is the actual cost so far, h an estimate (heuristic) of the cost remaining to the goal:

// useHeuristic = false turns A* into plain Dijkstra on the same grid.
public static (int Steps, int Expanded) Search(string[] grid, (int R, int C) start, (int R, int C) goal, bool useHeuristic)
{
    int rows = grid.Length, cols = grid[0].Length;
    int[,] g = new int[rows, cols];
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            g[r, c] = int.MaxValue;

    // Manhattan distance never overestimates with 4-way moves of cost 1: admissible.
    int H((int R, int C) p) => useHeuristic ? Math.Abs(p.R - goal.R) + Math.Abs(p.C - goal.C) : 0;

    PriorityQueue<(int R, int C), int> open = new();
    g[start.R, start.C] = 0;
    open.Enqueue(start, H(start));
    int expanded = 0;
    while (open.TryDequeue(out (int R, int C) cell, out int f))
    {
        if (f - H(cell) > g[cell.R, cell.C]) continue;
        expanded++;
        if (cell == goal) return (g[cell.R, cell.C], expanded);

        foreach ((int dr, int dc) in Directions)
        {
            int nr = cell.R + dr, nc = cell.C + dc;
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] == '#') continue;
            int candidate = g[cell.R, cell.C] + 1;
            if (candidate < g[nr, nc])
            {
                g[nr, nc] = candidate;
                open.Enqueue((nr, nc), candidate + H((nr, nc)));
            }
        }
    }

    return (-1, expanded);
}

The only requirement on the heuristic is that it be admissible: it must never overestimate the real remaining cost. On a four-way grid where every step costs 1, the Manhattan distance (row difference + column difference) ignores walls, so it can never be longer than the real path. With an admissible heuristic A* guarantees the shortest path; an overestimating heuristic may be faster but can find a wrong path. Choosing h = 0 turns A* into plain Dijkstra; the test compares both cases on the same grid.

On a 200 × 200 warehouse floor plan made of shelf blocks and aisles:

200x200 warehouse: Dijkstra steps=398 expanded=33,600; A* steps=398 expanded=1,845

Both find a path of the same length (398 steps); Dijkstra processes 33,600 cells while A* makes do with 1,845.

Measurement: Dijkstra and A*

[Benchmark(Baseline = true)]
public int Dijkstra() => GridAStar.Search(_floor, (0, 0), (199, 199), useHeuristic: false).Steps;

[Benchmark]
public int AStar() => GridAStar.Search(_floor, (0, 0), (199, 199), useHeuristic: true).Steps;

The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine; look at the ratios, not the absolute numbers.

| Method   | Mean      | Ratio | Allocated |
|--------- |----------:|------:|----------:|
| Dijkstra | 835.66 us |  1.00 | 164.47 KB |
| AStar    |  59.51 us |  0.07 | 188.52 KB |

A* is 14 times faster. Most of the allocation is the same for both: the 200 × 200 int[,] distance table (160 KB). A* allocates a little more because it fills and grows the queue in a different order. The gain depends entirely on the quality of the heuristic: the floor plan offers open aisles in the direction of the goal, so the Manhattan distance is a good estimate. In a maze where the goal sits behind a dead-end wall, A* can explore as many cells as Dijkstra.

Production Notes

Running Dijkstra from scratch on every request is expensive on real road networks. Map services use preprocessing techniques such as contraction hierarchies: the graph is processed once, then every query is answered in under a millisecond. At Bookstore scale (dozens of warehouses, hundreds of lines) plain Dijkstra is more than enough; caching the most frequently asked routes and clearing the cache when line costs change is a practical step.

Weight units and overflow. If costs are int, using int.MaxValue as "infinity" means dist[u] + cost can overflow. That is why our Bellman-Ford skips vertices with dist[u] == int.MaxValue; in Dijkstra we only relax from dequeued cities, which have a real distance. If you work with money, use decimal or a long in cents.

Multi-criteria routes. "Cheapest" and "fastest" usually differ. Define a single weight (cost + time × a coefficient) or run a constrained search (the cheapest route delivered within 48 hours); the latter goes beyond plain Dijkstra and requires adding the remaining time to the state.

Measure, then optimize. For a graph of hundreds of cities, using int-id arrays instead of Dictionary<string, int> gives a real speedup (the id mapping from the 15th post of the series), but costs readability. Do not do it until a profile says so.

Common Pitfalls

Forgetting the lazy deletion check. Without the if (d > dist[city]) continue; line the algorithm still finds the correct result, but stale entries are processed too and each one relaxes its neighbors again. On dense graphs the work multiplies, and callbacks like onSettled are called more than once for the same city; if that has a side effect like "add the city to the delivery plan", it is a straight bug.

Stopping when the target is added. If you stop the first time you update the target's distance (like stopping at 24 in step 5), you give a wrong answer while a cheaper route is still waiting in the queue. Stop only when the target is dequeued.

Dijkstra with negative weights. When refund, discount or "gain" edges enter the graph, Dijkstra silently gives wrong results; no exception, no warning. Add a guard that rejects negative weights when building the graph.

A non-admissible heuristic. If the grid also allows diagonal moves, the Manhattan distance can overestimate the real distance and A* returns a path that is not the shortest. Choose a heuristic that matches the movement model (Chebyshev or octile distance for diagonal moves).

A Small Experiment

★☆☆ Change Dijkstra to return distances to all cities without a target (Dictionary<string, int>) and compare the result with Bellman-Ford in a test.

★★☆ Remove the lazy deletion line and count how many times onSettled is called on a random graph with 10,000 vertices and 20 edges per vertex. Measure the times with and without the line using BenchmarkDotNet.

★★★ Add diagonal moves to the warehouse grid (cost as an integer in a 14/10 ratio instead of √2: straight 10, diagonal 14). Try the Manhattan, Chebyshev and octile heuristics; show with a test which one finds a wrong (longer) path.

Dijkstra found the cheapest path between two points. In the next post the question changes: which is the cheapest fiber network connecting all the offices? The answer is not a path but a tree; to build it we will first write Union-Find, which answers "are these two points already connected?" in almost constant time.