Ordered frontier and path · HTML
Set dist[s]=0. Relax u→v with w≥0 by cand=dist[u]+w. A minimum non-stale label popped from the heap is final.
Recognition signals
- The objective minimizes a sum of route cost, delay, or length.
- Every transition cost is known and nonnegative.
- Unequal weights destroy ordinary BFS layering.
- Single-source distances to one or many destinations are needed.
False friends
| Signal | Why it is different |
|---|
| Negative edge weight | A negative detour can improve an already popped label, invalidating Dijkstra's greedy proof. |
| Minimize the maximum step | The path aggregator is max rather than addition; use minimax-dijkstra. |
Core invariant
A non-stale popped label (d,u) is the smallest unsettled label, and nonnegative extensions cannot create a future route to u below d.
State, transition, and processing order
| Item | Definition |
|---|
| State | Tentative sum dist[v], min-heap entries (distance,node), and optional parent pointers. |
| Transition | For u→v,w compute nd=d+w; if nd improves dist[v], assign it and push the new label. |
| Frontier / order | A min-heap ordered by tentative distance; Python uses duplicate pushes plus lazy deletion instead of decrease-key. |
Python skeleton
import heapq
def dijkstra(graph, start, goal=None):
dist = {start: 0}
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d != dist.get(u):
continue
if goal is not None and u == goal:
return d
for v, w in graph.get(u, []):
if w < 0:
raise ValueError('negative edge')
nd = d + w
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist if goal is None else float('inf')
Correctness sketch
- Suppose a popped minimum fresh label u had a shorter route. On that route, the first unsettled vertex follows a settled predecessor that would have generated a smaller label, a contradiction.
- Relaxing every outgoing edge considers every path prefix capable of improving a destination.
- Skipping a stale heap entry discards only a superseded label, never the current best label.
Complexity
| Time | Space | Parameters |
|---|
| O((V+E) log H), commonly O(E log V) | O(V+H); lazy heaps can reach H=O(E) | V is vertices, E edges, and H simultaneous heap labels. A theoretical decrease-key heap keeps at most one handle per vertex; duplicate-push Python is also written O(E log E), with log E=O(log V) for simple graphs. |
Edge cases
- If source equals goal, its first pop returns zero.
- An unreachable goal returns infinity or a documented sentinel.
- Zero-weight edges are valid.
- Parallel edges are handled naturally by relaxation.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Pre-visiting the source | Initializing visited with start and then skipping visited pops discards the source itself. |
| Finalizing on push | A later route may improve a discovered vertex; finality belongs to a fresh pop. |
| Pushing without assigning dist | Heap insertion and dist assignment must occur in the same successful relaxation. |
Selection and exclusion rules
- Use BFS for equal weights, 0-1 BFS for binary weights, and Dijkstra for general nonnegative weights.
- For one destination, exit only when it is popped with a fresh label.
- In Python, prefer dist plus lazy deletion rather than emulating decrease-key.
| Relation | Template | Boundary |
|---|
| alternative | Grid dynamic programming | Nonnegative weighted movement in arbitrary directions contains cycles. |
| structural-analogy | K-way merge heap | The frontier is generated by state expansion and several paths can reach one state. |
| different path algebra | Minimax / bottleneck Dijkstra | Summation changes to minimizing the largest step. |
Original micro-example
| Part | Detail |
|---|
| Result | The minimum sum from s to a is 3. |
| Setup | s→a costs 7, s→b costs 2, and b→a costs 1. |
| Trace | Push a:7 and b:2; popping b improves a to 3; a:3 pops before stale a:7. |
Recall prompts
My notes