Lab 04 — Dijkstra (Network Delay Time)

Goal

Implement Dijkstra’s algorithm (lazy variant, binary heap) for single-source shortest path on a non-negative-weighted directed graph. After this lab you should be able to write Dijkstra from a blank screen in <8 minutes, including the staleness-skip line; recognize the non-negative-weight signal in <30 seconds; and adapt the template to “shortest path with constraints” (e.g., max K edges) by extending the state.

Background Concepts

Dijkstra’s algorithm computes the shortest path from a source s to every other node in a graph with non-negative edge weights. The core invariant: when a node u is extracted from the priority queue (heap), its tentative distance dist[u] is final. The proof relies on non-negativity: any other path to u must go through some node w not yet extracted, with dist[w] ≥ dist[u], and the path’s total length is dist[w] + (non-negative tail) ≥ dist[u].

Two variants:

  • Lazy: push every relaxation (new_dist, neighbor) to the heap; on pop, skip if new_dist > dist[neighbor] (stale entry). Heap holds up to E entries. Simpler.
  • Eager: maintain a decrease-key indexed heap; each node appears at most once. Faster constants, more code.

In interviews, lazy is the default. State that explicitly.

Interview Context

Dijkstra appears in the top 5 graph algorithms tested at FAANG. Network Delay Time (LC 743) is the canonical version, asked at Google, Amazon, and Bloomberg. Cheapest Flights (LC 787) is the constrained variant. The senior signal is: state “this is Dijkstra, weights are non-negative, lazy variant with binary heap, O((V+E) log V)” within the first two minutes, before writing code. Candidates who don’t articulate this and just dive in lose points even if the code works.

Problem Statement

You are given a network of n nodes labeled 1..n. A list times of edges where times[i] = (u, v, w) means it takes w time for a signal to travel from u to v. A signal is sent from node k. Return the minimum time for all nodes to receive the signal, or -1 if some node never receives it.

Constraints

  • 1 ≤ n ≤ 100, 1 ≤ |times| ≤ 6000
  • 1 ≤ u, v, k ≤ n; u ≠ v
  • 0 ≤ w ≤ 100
  • Edges are directed; possibly multi-edges.

Clarifying Questions

  1. Are weights non-negative? (Yes — Dijkstra applies.)
  2. Are nodes 1-indexed? (Yes — adjust array sizes accordingly.)
  3. Are duplicate edges possible? (Yes — they’re allowed; minimum-weight edge between (u, v) is what matters effectively.)
  4. Is the graph guaranteed connected? (No — return -1 if unreachable.)
  5. What’s the answer if the graph has only the source? (0 — already received.)

Examples

times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
→ 2  (signal reaches 1, 3 at time 1; 4 at time 2)

times = [[1,2,1]], n=2, k=1
→ 1

times = [[1,2,1]], n=2, k=2
→ -1

Initial Brute Force

Bellman-Ford: V - 1 rounds of relaxing all E edges. Time O(V · E). At V=100, E=6000: 6 × 10^5 ops — passes easily but is the wrong answer when the interviewer asks complexity.

Alternative brute force: BFS treating equal-weight edges. Wrong answers on weighted graphs unless all weights = 1.

Brute Force Complexity

Bellman-Ford: O(V · E) = 6 × 10^5. BFS-as-Dijkstra: incorrect for varying weights.

Optimization Path

Dijkstra with binary heap: O((V + E) log V) = ~5 × 10^4 with these constraints. The right answer.

For very dense graphs (E ~ V²), simple Dijkstra without a heap (just scan for the min unsettled node) is O(V²) and can be faster. Floyd-Warshall is O(V³) all-pairs — overkill for single-source, but valid here at V=100.

Final Expected Approach

  1. Build adjacency list from edge list. adj[u] is a list of (weight, neighbor) pairs.
  2. dist[i] = ∞ for all i except dist[k] = 0.
  3. Push (0, k) to a min-heap.
  4. While heap non-empty: pop (d, u); if d > dist[u], skip (stale); else relax all edges u → v: if d + w < dist[v], update and push.
  5. After the loop, max(dist[1..n]) is the answer; if any is ∞, return -1.

Data Structures Used

  • Adjacency list: dict[int, list[(int, int)]] or list[list[(int, int)]] indexed 1..n.
  • Distance array: list[int] of size n+1, init to inf.
  • Priority queue: Python’s heapq (min-heap).

Correctness Argument

Loop invariant: when (d, u) is popped from the heap with d == dist[u], that distance is final. Proof: any other path to u goes through some node w not yet popped (else dist[u] would have been updated to a smaller value). Since w is unsettled, dist[w] ≥ dist[u] (by heap order). The path’s total length is dist[w] + tail ≥ dist[u] (non-negativity of tail). So dist[u] is optimal.

Termination: each node is finalized at most once (the staleness-skip ensures repeated pops don’t re-relax). At most V finalizations + E heap pushes: O((V + E) log V).

Complexity

OperationTimeSpace
Build adjacencyO(V + E)O(V + E)
DijkstraO((V + E) log V)O(V + E) heap
TotalO((V + E) log V)O(V + E)

Implementation Requirements

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((w, v))
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for w, v in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    ans = max(dist[1:n+1])
    return -1 if ans == INF else ans

Tests

  • Standard: 4-node star → 2.
  • Disconnected: source can’t reach a node → -1.
  • Single node, source = only node → 0.
  • Duplicate edges: pick min weight on relaxation.
  • Self-loop (problem disallows but defend): doesn’t affect answer; skip.
  • Stress: V=100, E=6000 random, compare against Bellman-Ford reference.
  • Adversarial: dense graph forcing many heap pushes.

Follow-up Questions

  1. “Now find shortest path with at most K edges.” (LC 787) → Bellman-Ford OR Dijkstra with state (node, edges_used). See Lab 05.
  2. “Now weights can be negative.” → Dijkstra is wrong; use Bellman-Ford.
  3. “Find path with maximum probability” (LC 1514) → Dijkstra with max-heap and product (or -log weights and standard Dijkstra).
  4. “All-pairs shortest path.” → Run Dijkstra from every node, O(V · (V+E) log V), or Floyd-Warshall O(V³).
  5. “Graph evolves online.” → Recompute on each query, or use dynamic shortest-path structures (advanced).

Product Extension

Network monitoring tools use Dijkstra-like algorithms for path-cost estimation. Routing protocols like OSPF use Dijkstra (link-state routing) to compute shortest paths in IP networks. CDN edge selection, traffic engineering, and request routing in microservices meshes all rely on shortest-path computations parameterized by latency, cost, or QoS.

Language/Runtime Follow-ups

  • Python: heapq is a min-heap; for max-heap, negate weights or use tuples (-w, ...). Tuple comparison is element-by-element — (d, u) compares by d first.
  • Java: PriorityQueue<int[]> with comparator on the weight index, or PriorityQueue<long[]> if weights overflow. Don’t use Pair from JavaFX (deprecated).
  • Go: container/heap requires implementing the heap.Interface. Tedious; many candidates inline a slice-based heap. For small N, even O(V²) Dijkstra without heap is fine.
  • C++: priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> for min-heap. Or negate weights with default max-heap.
  • JS/TS: no built-in heap. Use a library (heap-js) or hand-roll. For small N, an O(V²) scan is acceptable.

Common Bugs

  1. Forgetting the staleness check if d > dist[u]: continue — the heap pops the same node multiple times after stale updates; without the skip, you re-relax incorrectly and blow up complexity.
  2. Pushing (u, dist[u]) instead of (dist[u], u) — heap orders on first element, so distance must come first.
  3. 1-indexed vs 0-indexed off-by-one. The problem is 1-indexed; size arrays at n + 1.
  4. Initial dist not set to ∞ — using 0 makes the source’s neighbors look “already optimal”.
  5. Pushing the source to the heap but forgetting to set dist[source] = 0.
  6. Returning min(dist) (which catches the unreachable -∞) instead of max(dist) (which is the actual question).
  7. Negative weights — Dijkstra silently produces wrong answers; you won’t see this fail unless you stress-test.

Debugging Strategy

Print the heap contents and dist array after each pop. Verify the popped distance equals dist[u] for non-stale entries. For wrong answers, trace a specific node v where dist[v] is wrong: identify the predecessor u that should have relaxed it; check that (d_u + w_uv) is computed correctly. For complexity blowup, check that the staleness skip is present and triggers.

Mastery Criteria

  • Recognized “shortest path with non-negative weights” as Dijkstra in <30 seconds.
  • Wrote Dijkstra from blank screen with the staleness check in <8 minutes.
  • Stated O((V + E) log V) complexity unprompted.
  • Articulated why Dijkstra fails on negative weights in <30 seconds.
  • Solved LC 743 in <15 minutes from cold start.
  • Solved LC 1631 (Path With Minimum Effort) in <20 minutes by adapting weights = max along path.
  • Solved LC 778 (Swim in Rising Water) in <20 minutes.
  • Stated lazy vs eager difference in <30 seconds.