Dijkstra Theory

Definition

Given a weighted graph G = (V, E) with non‑negative edge weights w(u,v) ≥ 0 and a source vertex s, Dijkstra's algorithm computes the shortest path distance dist[v] from s to every vertex reachable from s. It maintains a frontier of tentative distances and progressively finalizes (settles) the minimum one.

Key Concepts

• Relaxation: Attempt to improve a tentative distance via an edge (u,v) by checking if dist[u] + w(u,v) < dist[v].
• Settled Set: Vertices whose shortest distances are finalized; no future relaxation can improve them.
• Priority Queue: Orders frontier vertices by current tentative distance.
• Stale Entries: Older queue items with outdated distances; skipped when extracted.
• Greedy Choice: Always settle the closest unsettled vertex first—safe due to non‑negative weights.

Algorithm Steps

1. Initialize dist[v] = ∞, parent[v] = NIL for all vertices; dist[source] = 0.
2. Push (source,0) into a min-priority queue keyed by distance.
3. While queue not empty extract the vertex u with minimum tentative distance.
4. If u already settled (visited) skip (stale entry).
5. Mark u settled; its distance is now final.
6. For each outgoing edge (u,v,w) perform relaxation: if dist[u] + w < dist[v], update dist[v], parent[v]=u, push (v, dist[v]) into queue.
7. Repeat until queue empty or target settled (early exit for single-destination queries).
8. Reconstruct paths by following parent pointers backwards from a destination.

Data Structures

Using duplicate insertions (lazy deletion) avoids implementing decrease-key at cost of extra heap size.

Time & Space Complexity

Fibonacci heap achieves O(E + V log V); rarely worth complexity in practice. With dense graphs, adjacency matrix + simple selection yields O(V^2).

Pseudocode

1Dijkstra(G, source):
2  for each vertex v in G:
3    dist[v] ← ∞
4    parent[v] ← NIL
5    visited[v] ← false          // settled / finalized flag
6  dist[source] ← 0
7  PQ ← empty min-priority queue (key = dist)
8  insert (source, 0) into PQ
9  while PQ not empty:
10    (u, du) ← extract-min(PQ)   // smallest tentative distance
11    if visited[u]:              // stale entry check (optional optimization)
12      continue
13    visited[u] ← true           // u is now settled; dist[u] is final
14    for each edge (u, v, w) outgoing from u:
15      if visited[v]:
16        continue                // already finalized
17      if dist[u] + w < dist[v]:  // relaxation
18        dist[v] ← dist[u] + w
19        parent[v] ← u
20        insert (v, dist[v]) into PQ   // may create duplicate stale entries
21  return dist, parent

Applications

• GPS / road network routing (non‑negative distances)
• Network latency / bandwidth path optimization
• Game AI pathfinding (when weights non‑negative)
• Preprocessing for Johnson's algorithm (reweight + run)
• Emergency response / logistics planning
• Telecom routing & QoS calculations

Edge Cases & Pitfalls

• Negative Edge: Invalidates correctness; use Bellman-Ford or Johnson.
• Negative Cycle: Not detectable by Dijkstra; distances undefined.
• Unreachable Vertices: Remain dist = ∞ (retain NIL parent).
• Overflow: Use large sentinel instead of Number.MAX_VALUE to avoid addition overflow in JS.
• Dense Graph Choice: O(V^2) array implementation might outperform heap.

Example Problems

• Find shortest driving time between two cities
• Compute routing table from a source router
• Minimum energy path in weighted grid (non‑negative)
• Game map navigation with terrain cost modifiers
• Delivery path planning with road distances