Dijkstra in C#: PriorityQueue, A*, and Why Negative Edges Break It

Problem Context

Dijkstra's algorithm (Edsger Dijkstra, 1959, designed in 20 minutes at a café in Amsterdam) is the workhorse of weighted shortest paths — every routing protocol, every map app, every microservice mesh that picks the "cheapest" downstream uses a Dijkstra variant. It's also the algorithm everyone gets almostright: the textbook version is O((V + E) log V) with a binary heap, but the naive implementation is O(V²) and the "just push and ignore stale entries" trick is the practical sweet spot in 2026.

The non-negotiable assumption: all edge weights must be non-negative.The moment a single edge is negative, Dijkstra's greedy choice is wrong and you need Bellman-Ford or SPFA. This guide is the implementation that actually ships, plus the variants (A*, K-shortest, multi-source) that come up in production.

Concept Explanation

Dijkstra in one sentence: repeatedly extract the unvisited vertex with the smallest tentative distance, relax all its outgoing edges, mark it visited. Greedy + non-negative weights guarantees correctness — once you visit a vertex, you can never reach it more cheaply later, because all future paths add non-negative weight.

Three implementation choices:

• Array of distances + linear scan — O(V²). Best for dense graphs.
• Binary heap (PriorityQueue) — O((V + E) log V). Best for sparse graphs.
• Fibonacci heap — O(E + V log V) theoretically. Constants are awful; nobody uses this in production.

flowchart LR
    Q["Shortest path?"] --> N{"Negative edges?"}
    N -->|yes| BF["Bellman-Ford<br/>O(V·E)"]
    N -->|no| H{"Have a heuristic?"}
    H -->|yes, admissible| AS["A*<br/>(Dijkstra + h)"]
    H -->|no| W{"Edges weighted?"}
    W -->|no| BFS["BFS<br/>O(V + E)"]
    W -->|yes| DJK["Dijkstra<br/>+ binary heap"]
    DJK --> P{"Sparse graph?"}
    P -->|yes| HEAP["O((V+E) log V)<br/>PriorityQueue"]
    P -->|no, dense| ARR["O(V²)<br/>linear scan"]

    style DJK fill:#16a34a,color:#fff,stroke:#15803d
    style BF fill:#dc2626,color:#fff,stroke:#b91c1c

Implementation

Step 1: The production version — PriorityQueue + skip-stale

public static Dictionary<int, int> Dijkstra(
    Dictionary<int, List<(int to, int weight)>> graph, int source)
{
    var dist = new Dictionary<int, int> { [source] = 0 };
    var pq = new PriorityQueue<int, int>();
    pq.Enqueue(source, 0);

    while (pq.TryDequeue(out var u, out var d))
    {
        if (d > dist[u]) continue;            // ← skip stale entries
        foreach (var (v, w) in graph.GetValueOrDefault(u) ?? new())
        {
            int nd = d + w;
            if (nd < dist.GetValueOrDefault(v, int.MaxValue))
            {
                dist[v] = nd;
                pq.Enqueue(v, nd);            // push the new (possibly duplicate) entry
            }
        }
    }
    return dist;
}

Step 2: Reconstruct the path, not just the distance

public static (Dictionary<int, int> dist, Dictionary<int, int> prev) DijkstraWithPath(
    Dictionary<int, List<(int to, int weight)>> graph, int source)
{
    var dist = new Dictionary<int, int> { [source] = 0 };
    var prev = new Dictionary<int, int>();
    var pq = new PriorityQueue<int, int>();
    pq.Enqueue(source, 0);

    while (pq.TryDequeue(out var u, out var d))
    {
        if (d > dist[u]) continue;
        foreach (var (v, w) in graph.GetValueOrDefault(u) ?? new())
        {
            int nd = d + w;
            if (nd < dist.GetValueOrDefault(v, int.MaxValue))
            {
                dist[v] = nd;
                prev[v] = u;                  // ← remember predecessor
                pq.Enqueue(v, nd);
            }
        }
    }
    return (dist, prev);
}

public static List<int> RebuildPath(Dictionary<int, int> prev, int source, int target)
{
    var path = new List<int>();
    for (int n = target; n != source; n = prev[n])
    {
        if (!prev.ContainsKey(n)) return new();   // unreachable
        path.Add(n);
    }
    path.Add(source);
    path.Reverse();
    return path;
}

Step 3: A* — Dijkstra with a heuristic

// f(n) = g(n) + h(n)
//   g(n) = actual cost from source to n  (known)
//   h(n) = estimated cost from n to goal (heuristic)
// h must be ADMISSIBLE: never overestimates the true remaining cost.
// For maps: straight-line distance. For grids: Manhattan/Chebyshev.

public static int? AStar(
    Dictionary<int, List<(int to, int weight)>> graph,
    int source, int goal, Func<int, int> heuristic)
{
    var g = new Dictionary<int, int> { [source] = 0 };
    var pq = new PriorityQueue<int, int>();
    pq.Enqueue(source, heuristic(source));

    while (pq.TryDequeue(out var u, out _))
    {
        if (u == goal) return g[u];
        foreach (var (v, w) in graph.GetValueOrDefault(u) ?? new())
        {
            int ng = g[u] + w;
            if (ng < g.GetValueOrDefault(v, int.MaxValue))
            {
                g[v] = ng;
                pq.Enqueue(v, ng + heuristic(v));   // f = g + h
            }
        }
    }
    return null;   // unreachable
}

Step 4: Multi-source Dijkstra — "nearest of any source"

// E.g., for each city, find the distance to the nearest hospital.
// Trick: seed the priority queue with ALL sources at distance 0.
public static Dictionary<int, int> MultiSourceDijkstra(
    Dictionary<int, List<(int to, int weight)>> graph, IEnumerable<int> sources)
{
    var dist = new Dictionary<int, int>();
    var pq = new PriorityQueue<int, int>();
    foreach (var s in sources) { dist[s] = 0; pq.Enqueue(s, 0); }
    while (pq.TryDequeue(out var u, out var d))
    {
        if (d > dist[u]) continue;
        foreach (var (v, w) in graph.GetValueOrDefault(u) ?? new())
        {
            int nd = d + w;
            if (nd < dist.GetValueOrDefault(v, int.MaxValue))
            { dist[v] = nd; pq.Enqueue(v, nd); }
        }
    }
    return dist;
}

Step 5: Bellman-Ford — when negative edges are unavoidable

// O(V·E). Detects negative cycles.
public static (Dictionary<int, int>? dist, bool negCycle) BellmanFord(
    int V, IEnumerable<(int u, int v, int w)> edges, int source)
{
    var dist = Enumerable.Range(0, V).ToDictionary(k => k, _ => int.MaxValue);
    dist[source] = 0;

    for (int i = 0; i < V - 1; i++)
        foreach (var (u, v, w) in edges)
            if (dist[u] != int.MaxValue && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;

    // Detect negative cycle: one more pass; any further relaxation = cycle
    foreach (var (u, v, w) in edges)
        if (dist[u] != int.MaxValue && dist[u] + w < dist[v])
            return (null, true);

    return (dist, false);
}

Step 6: Sanity-check your edge weights and graph density

Before you implement Dijkstra, answer:

1. Are all edges non-negative?       NO → Bellman-Ford
2. Are weights all 0 or 1?           YES → 0-1 BFS (deque, O(V+E))
3. Are weights all equal?            YES → BFS, no priority queue needed
4. Do you have a goal heuristic?     YES → A* (much faster in practice)
5. Is the graph dense (E ~ V²)?      YES → array-based O(V²) beats heap
6. Is V tiny (< 500)?               YES → Floyd-Warshall for all-pairs O(V³)

Pitfalls

1. Negative edges. Dijkstra silently produces wrong answers — no exception, no warning. Validate inputs or use Bellman-Ford if negatives are possible.

2. Trying to update priorities in PriorityQueue. .NET's heap doesn't support decrease-key. The clean trick: push a new entry with the lower priority and skip stale entries on dequeue (if (d > dist[u]) continue). Memory is O(E) instead of O(V), but it's simple and fast.

3. Initialising distances to 0 instead of int.MaxValue. Then every vertex looks reachable at cost 0 and you produce nonsense. Use int.MaxValue + a guard against overflow when relaxing (if (dist[u] != int.MaxValue)).

4. Inadmissible A* heuristic. If h overestimates the true remaining cost, A* finds apath but not necessarily the shortest. Straight-line distance is always admissible for maps; learned heuristics often aren't.

5. Building the graph wrong.Forgetting to add the reverse edge for an undirected graph means half your paths don't exist. Add both directions explicitly.

6. Recomputing Dijkstra from every source for all-pairs.If V is small (< 500), Floyd-Warshall's O(V³) is simpler, faster in practice, and handles negative edges (no negative cycles) naturally.

Practical Takeaways

• Use PriorityQueue<int, int>+ the "skip stale" pattern. It's the simplest correct Dijkstra in .NET.
• Always store predecessors if you need the path, not just the distance.
• Validate that weights are non-negative. If they aren't, switch to Bellman-Ford.
• Use A* whenever you have an admissible heuristic — it's dramatically faster than plain Dijkstra in practice.
• Multi-source Dijkstra: seed the queue with all sources at distance 0. One pass gives you nearest-of-any-source.
• Special cases beat general Dijkstra: 0-1 BFS for binary weights, BFS for unweighted, Floyd-Warshall for small all-pairs.
• Profile before micro-optimizing — for V < 10k the heap version is plenty fast; the constant factor matters more than the asymptotic.