Dijkstra's Algorithm with Binary Heap

Worked Solution

How to Think About It: Dijkstra's is the workhorse of shortest-path algorithms for nonnegative weights. The core idea is greedy: the vertex with the smallest tentative distance is guaranteed to already have its true shortest distance locked in, because no future relaxation through a longer path can improve it (this is where nonnegativity is critical). A binary heap lets you extract the minimum efficiently, and the "lazy deletion" pattern (push duplicates and skip stale entries) is the cleanest way to implement it without a decrease-key operation.

Algorithm: Maintain an array $\text{dist}[]$ initialized to $\infty$ except $\text{dist}[s] = 0$, and a predecessor array $\text{prev}[]$ for path reconstruction. Push $(0, s)$ into a min-heap. Repeatedly extract the minimum-distance pair $(d, u)$. If $d > \text{dist}[u]$, this is a stale entry -- skip it. Otherwise, for each neighbor $v$ of $u$, if $\text{dist}[u] + w(u,v) < \text{dist}[v]$, update $\text{dist}[v]$, set $\text{prev}[v] = u$, and push $(\text{dist}[v], v)$ into the heap. Continue until the heap is empty.

Code:

```python import heapq from typing import List, Tuple, Optional

def dijkstra(n: int, edges: List[Tuple[int, int, int]], source: int ) -> Tuple[List[float], List[Optional[int]]]: # Build adjacency list adj = [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w))

dist = [float('inf')] * n prev = [None] * n dist[source] = 0 heap = [(0, source)] # (distance, vertex)

while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue # stale entry, skip for v, w in adj[u]: nd = d + w if nd < dist[v]: dist[v] = nd prev[v] = u heapq.heappush(heap, (nd, v))

return dist, prev

def reconstruct_path(prev: List[Optional[int]], target: int) -> List[int]: if prev[target] is None and target != 0: return [] # unreachable path = [] cur = target while cur is not None: path.append(cur) cur = prev[cur] return path[::-1] ```

Correctness Proof (sketch):

We prove by induction that when a vertex $u$ is extracted from the heap, $\text{dist}[u]$ equals the true shortest-path distance $\delta(s, u)$.

• *Base case:* The source $s$ is extracted first with $\text{dist}[s] = 0 = \delta(s, s)$.
• *Inductive step:* Suppose all previously extracted vertices have correct distances. When $u$ is extracted, assume for contradiction that $\text{dist}[u] > \delta(s, u)$. Then there exists a shorter path $P$ from $s$ to $u$. Let $(x, y)$ be the first edge on $P$ where $x$ has been extracted but $y$ has not. Since $x$ was extracted earlier, $\text{dist}[x] = \delta(s, x)$ by hypothesis, and edge $(x, y)$ was relaxed when $x$ was processed, so $\text{dist}[y] \leq \delta(s, x) + w(x, y) = \delta(s, y)$. But since all weights are nonnegative, $\delta(s, y) \leq \delta(s, u) < \text{dist}[u]$, so $y$ would have been extracted before $u$ -- contradiction.

Why negative edges break this: If an edge $(x, y)$ has negative weight, then $\delta(s, y) \leq \delta(s, x) + w(x,y)$ no longer implies $\delta(s, y) \leq \delta(s, u)$. A vertex extracted with some distance might later be reachable via a cheaper path through a negative edge that was not yet discovered.

Edge Cases: - *Disconnected vertices:* Remain at $\text{dist} = \infty$, $\text{prev} = \text{None}$. The algorithm handles this naturally since they are never pushed onto the heap. - *Parallel edges:* The adjacency list stores all of them. When relaxing, the shortest one wins automatically. - *Zero-weight edges:* Perfectly fine -- they do not violate the nonnegative assumption. The algorithm treats them like any other edge. A cycle of zero-weight edges does not cause infinite loops because we skip stale heap entries. - *Self-loops:* A self-loop $(u, u, w)$ with $w \geq 0$ never improves $\text{dist}[u]$, so it is harmlessly skipped.

Complexity: $O(m \log n)$ time -- each edge causes at most one heap insertion, and each extraction is $O(\log n)$. Space is $O(n + m)$ for the adjacency list and heap.

Answer: Dijkstra's algorithm with a binary heap computes SSSP in $O(m \log n)$ time for nonnegative weights. The greedy property -- extracting the minimum-distance vertex commits to its final distance -- holds precisely because edge weights are nonnegative.