Intro

Dijkstra's algorithm computes shortest paths from a single source to all other nodes in a graph with non-negative edge weights. It works by greedily finalizing the node with the smallest tentative distance, then relaxing its outgoing edges to improve neighbor distances. The greedy choice is correct because non-negative weights guarantee that no future path through an unfinalized node can beat the current shortest — once a node is extracted from the priority queue, its distance is final.

Use Dijkstra for routing (network shortest paths, GPS navigation), cost minimization (cheapest flight itinerary), and resource planning where edge costs represent real quantities like latency, distance, or price. It does not work when edges have negative weights — that breaks the finalization invariant and requires Bellman-Ford instead.

How It Works

1. Initialize dist[source] = 0 and dist[v] = ∞ for all other nodes. Push (0, source) into a min-priority queue.
2. Extract the node v with the smallest tentative distance. If the extracted distance exceeds dist[v], skip it (stale entry from lazy deletion).
3. For each outgoing edge (v, u, w), check if dist[v] + w < dist[u]. If so, update dist[u] and push (dist[v] + w, u).
4. Repeat until the queue is empty. Optionally maintain a parent[] array to reconstruct paths by walking backward from the target.

Complexity: O((V + E) log V) with a binary heap. On dense graphs where E ≈ V², a simple array scan gives O(V²) which is faster than heap overhead.

graph TD
  A[Input graph with nonnegative weights and source s] --> B[Initialize dist to INF]
  B --> C[Set dist of s to 0]
  C --> D[Push pair 0 and s into priority queue]
  D --> E{PQ empty}
  E -->|No| F[Extract min pair d and v]
  F --> G{d differs from dist of v}
  G -->|Yes| E
  G -->|No| H[For each edge from v to u with weight w]
  H --> I{dist of v plus w less than dist of u}
  I -->|Yes| J[Update dist of u]
  J --> K[Push updated pair into priority queue]
  K --> H
  I -->|No| H
  E -->|Yes| L[Output dist and optionally parent]

Example

Graph edges: A-B(2), A-C(5), B-C(1), B-D(4), C-D(1)
Source: A

Step 1: Extract A (dist=0). Relax A→B: dist[B]=2. Relax A→C: dist[C]=5.
Step 2: Extract B (dist=2). Relax B→C: 2+1=3 < 5, update dist[C]=3. Relax B→D: dist[D]=6.
Step 3: Extract C (dist=3). Relax C→D: 3+1=4 < 6, update dist[D]=4.
Step 4: Extract D (dist=4). No unfinalized neighbors.

Final: dist[A]=0, dist[B]=2, dist[C]=3, dist[D]=4
Shortest A→D path: A→B→C→D (cost 4)

Pitfalls

Negative Edge Weights Break Correctness

• What goes wrong: Dijkstra finalizes a node's distance on extraction, but a later path through a negative-weight edge can produce a shorter distance to an already-finalized node, giving wrong results.
• Why it happens: the greedy invariant assumes adding more edges can only increase path cost. Negative weights violate this assumption.
• How to avoid it: validate all edge weights are ≥ 0 before running Dijkstra. Use Bellman-Ford when negative edges exist.

Stale Priority Queue Entries

• What goes wrong: without decrease-key support, updating a node's distance pushes a new entry while the old one remains. Processing stale entries wastes time and can cause incorrect relaxation if the guard check is missing.
• Why it happens: standard binary heaps in most languages do not support decrease-key, so lazy deletion is the common workaround.
• How to avoid it: always check if extracted_dist > dist[v]: skip before processing a node. This guard is what makes lazy deletion correct.

Dense Graph Performance

• What goes wrong: on dense graphs (E ≈ V²), the heap-based approach becomes O(V² log V), slower than the O(V²) array-scan version.
• Why it happens: heap overhead (log V per push) exceeds its benefit when nearly every node pair has an edge.
• How to avoid it: for dense graphs, use the simple array-scan variant that picks the minimum in O(V) per iteration, giving O(V²) total.

Tradeoffs

Questions

References

• Dijkstra's algorithm -- encyclopedic overview covering correctness proof, complexity analysis, and historical context (Wikipedia)
• Dijkstra on sparse graphs -- implementation guide with adjacency list, binary heap, and code examples for competitive programming (cp-algorithms)