p63 — Network Delay Time

Source: LeetCode 743 · Medium · Topics: Graph, Dijkstra, Shortest Path Companies (2024–2025): Amazon (high), Google (high), Microsoft (high), Meta (medium-high), Uber (medium-high) Loop position: Dijkstra canonical. Single-source shortest path on a non-negative-weight directed graph. Heap version O((V+E) log V).

1. Quick Context

Network: n nodes 1..n, edges times[i] = [u, v, w] directed u → v with travel time w. From source k, return the time for the signal to reach ALL nodes (= max shortest-path distance). Return -1 if any node unreachable.

Standard Dijkstra:
dist = [INF] * (n+1); dist[k] = 0
heap = [(0, k)]
while heap:
    d, u = heappop(heap)
    if d > dist[u]: continue   # stale entry
    for v, w in adj[u]:
        if d + w < dist[v]:
            dist[v] = d + w
            heappush(heap, (d+w, v))
answer = max(dist[1..n]) if all reachable else -1

O((V + E) log V) with binary heap; O(E + V log V) with Fibonacci heap (rarely used in practice).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/network-delay-time/

STOP. 25-min timer.

3. Prerequisite Concepts

• Adjacency list of weighted edges.
• heapq as a min-heap (Python only has min-heap natively).
• Concept of “stale heap entry” — same node can be pushed multiple times; skip when popped distance > current dist.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: All-targets shortest path from k; answer is the max distance.

2. Clarify: Edge weights non-negative? (Yes — Dijkstra requires this.) Directed. 1-indexed nodes.

3. Examples:

• times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → 2.
• Single isolated node not reachable → -1.

5. Brute force: Bellman-Ford O(V·E). Or BFS-with-priority (= Dijkstra).

6. Target: O((V+E) log V).

7. Pattern: Dijkstra.

8. Develop: see solution.py.

9. Test: disconnected; one node; self-loops; multiple edges same pair; LC examples.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Dijkstra — the cut property

Cut property: when we pop (d, u) from the heap with d == dist[u], this d is the true shortest-path distance to u.

Proof sketch: All popped distances are non-decreasing (heap property). Suppose dist[u] were larger than the true shortest distance — then on the true shortest path from k to u, the predecessor p of u was popped earlier with the true dist[p], and we would have relaxed dist[u] := dist[p] + w(p, u) to the correct value, contradiction. This argument requires non-negative weights — a negative edge (p, u, w<0) could decrease dist[u] after p is popped, breaking the invariant.

6.2 Why Dijkstra fails on negative edges

Counterexample: edges A→B(2), A→C(3), C→B(-2). From A: Dijkstra pops B(2) first, finalizes dist[B]=2. Later finds C→B = 3-2 = 1. Wrong.

For graphs with negative edges (but no negative cycles), use Bellman-Ford O(V·E) or, if you need many sources, Johnson’s algorithm (Bellman-Ford reweighting + Dijkstra per source).

6.3 Stale entries — the “if d > dist[u]: continue” line

heapq doesn’t support decrease-key. When a shorter path is found, we push (new_d, u) AGAIN; the old entry remains in the heap. When the old (larger) entry is popped, skip via the staleness check. Without it, you’d re-relax outgoing edges from u redundantly — correctness OK but performance degrades.

Alternative: use IndexedHeap / heapdict for true decrease-key, common in production graph libs (e.g., NetworkX).

6.4 SSSP variants you should know

6.5 A* — Dijkstra with a heuristic

A* is Dijkstra where the priority key is dist[u] + h(u) instead of dist[u]. With an admissible heuristic (h(u) ≤ true_dist_to_target), A* finds the optimal path while exploring fewer nodes. Used in path-finding (games, routing).

When h ≡ 0, A* degenerates to Dijkstra. When h is perfect, A* is greedy best-first.

6.6 Bidirectional Dijkstra

For shortest path between two specific nodes (not all targets), run Dijkstra from both source and target simultaneously; stop when the search frontiers meet. Cuts the effective explored area roughly in half. Standard in production routing (Google Maps, OpenStreetMap).

6.7 0/1 BFS — the deque trick

If all edge weights are 0 or 1, use a deque: push weight-0 edges to the front, weight-1 to the back. Achieves O(V + E) without a heap. Useful for grid problems where some moves are “free.”

6.8 Lower bound

SSSP on directed graphs with non-negative weights has no known O(E) algorithm in the general case (matter of open research). Thorup’s RAM-model O(E) algorithm exists for undirected graphs (1999). For typical problem sizes, binary-heap Dijkstra is the practical choice.

7. Anti-Pattern Analysis

1. Use Dijkstra on a graph with negative edges — Silently wrong; use Bellman-Ford.
2. Forget the staleness check — Correctness OK, performance degrades to O(E²/V·log V) worst case.
3. Build a max-heap by negating distances when you mean min-heap — Python heapq is already min-heap; double-negation is a common cause of subtle bugs.
4. Re-relax already-finalized nodes — happens without staleness check; bloats runtime.
5. Forget unreachable nodes — return -1 (or INF) when max(dist) == INF; off-by-one if you sum instead.
6. 1-indexed vs 0-indexed off-by-one — LC 743 is 1-indexed; allocate dist[n+1] or shift.
7. Multi-edge between same pair — keep all in adjacency list; Dijkstra naturally takes the min.

8. Skills & Takeaways

• Dijkstra with binary heap + staleness check.
• Cut property as proof tool.
• SSSP algorithm-family awareness (when to use which).
• A* and bidirectional Dijkstra for production routing.
• 0/1 BFS for weight ∈ {0, 1} graphs.

9. When to Move On

• Implement Dijkstra cold in 12 min.
• Solve LC 743, 787 (Cheapest Flights with K stops — see p64), 1631 (Path With Minimum Effort).
• Articulate cut property in 60 seconds.
• Explain why Dijkstra fails on negative edges with a concrete example.
• Know which algorithm to choose given weight constraints.

10. Company Context

• Amazon: L6 onsite; productized as “warehouse routing.”
• Google: L5/L6; Maps team adjacent; A* and bidirectional Dijkstra extensions.
• Microsoft: L65+; Azure routing.
• Uber: L5; ride-matching ETA = SSSP on road network.
• Meta: E5; social-graph distance variants.

Scorecard for strong: “Standard Dijkstra with staleness check; articulated cut property; mentioned A, bidirectional, and Bellman-Ford for negative edges.”*

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): Correct Dijkstra, staleness check, returns max dist or -1.
• Senior (L5): + A* with admissible heuristic + 0/1 BFS for weights {0,1} + LC 787 K-stops variant.
• Staff (L6): + bidirectional Dijkstra for s-t queries + Johnson’s algorithm + production routing engines (CRP, contraction hierarchies).
• Principal (L7+): + Thorup’s O(E) undirected SSSP + multi-modal routing (transit + walking + driving) + ALT/landmark preprocessing + scale-time tradeoffs in road networks.

13. Follow-up Q&A

Q1: What if some edge weights are negative (but no negative cycles)? A1: Bellman-Ford in O(V·E). Or run V iterations of edge relaxation; Bellman-Ford also detects negative cycles (a (V+1)-th relaxation that still updates means negative cycle exists).

Q2: All-pairs shortest path on a small graph. A2: Floyd-Warshall O(V³). For large sparse graphs, run Dijkstra from each node: O(V · (V+E) log V).

Q3: Find the shortest path (the sequence of nodes), not just its length. A3: Maintain parent[v] = the predecessor when dist[v] was last relaxed. Walk back from target.

Q4: K shortest paths (LC 882, Eppstein). A4: Modify Dijkstra to keep the K best distances per node (or use Eppstein’s O(E + V log V + K)).

Q5: Negative cycle on a path — what’s “shortest”? A5: Undefined (you could loop the negative cycle infinitely many times). Bellman-Ford signals this.

14. Solution Walkthrough

See solution.py:

• network_delay_dijkstra — heap-based Dijkstra with staleness check.
• network_delay_bellman_ford — V-iteration relaxation (oracle for verification; works with negative weights too).
• network_delay_brute — BFS-style exhaustive DP relaxation until stable.

15. Beyond the Problem

Principal code review: “Dijkstra is the algorithm. Every routing service in the world — Google Maps, Uber dispatch, Cisco’s OSPF protocol, Bitcoin’s Lightning Network path-finding — sits on top of some variant of it. The toy version you write in an interview runs in microseconds on a 100-node graph; the production version on the world road graph (~50M nodes, ~150M edges) needs Contraction Hierarchies, Customizable Route Planning, ALT landmarks, transit indices — all built atop Dijkstra. The cut property you should be able to prove on a whiteboard is the same property that makes those production optimizations correct. Memorize the code; understand the proof; respect the depth.”