Skip-stale pattern, path reconstruction, Bellman-Ford fallback.

Dijkstra in C# — PriorityQueue, A*, Negative Edges

Dijkstra finds shortest paths from a source in weighted graphs with non-negative edge weights. The greedy approach: always relax the minimum-distance unvisited node. .NET PriorityQueue<TElement, TPriority> supports this directly with O(log n) Enqueue/Dequeue. The skip-stale optimisation avoids a separate "visited" set. A* adds a heuristic to guide search toward the destination. Bellman-Ford handles negative weights at O(VE) cost.

Interactive Pipeline Flow

UnderstandImplementOptimise

📍 Source — dist[src]=0

Initialise: dist[source] = 0, all other dist[] = int.MaxValue. Enqueue (source, 0) into min-heap PriorityQueue.

Architecture Diagrams

Why skip-stale avoids a separate visited[] array.

Loading diagram...

Key Design Decisions

⚡Skip-stale > visited[] for sparse graphs

The skip-stale pattern allows multiple entries per node in PriorityQueue. Stale entries are cheap to skip, and no visited HashSet is needed.

🚫Dijkstra fails with negative weights

Negative edges break the greedy invariant. Use Bellman-Ford (O(VE)) for graphs with negative-weight edges. Johnson's algorithm for all-pairs.

🎯A* for geographic / grid pathfinding

With a Manhattan or Euclidean distance heuristic, A* explores far fewer nodes than Dijkstra on grid-based maps.

Discussion