Network Delay Time

You'll use Dijkstra's algorithm: always settle the closest node you haven't settled yet, using a min-heap. You need adjacency lists and Python's heapq. Related chapter: weighted shortest paths.

1. The problem

You get a network of nodes numbered 1 to n. Each [u, v, w] is a one-way link from u to v that takes w time units. Every w is zero or more. A signal starts at node k and spreads along the links. Return the time when every node has the signal, or −1 if some node never gets it. No link repeats. Don't change the input. LeetCode 743.

2. A correct baseline

Go over every link again and again. Each round, a node's best time can improve by using one more link. A shortest route never needs to visit a node twice, so it uses at most n − 1 links, and n − 1 rounds are enough. This is called Bellman–Ford.

def baseline(times, n, k):
    distance = [float('inf')] * (n + 1)
    distance[k] = 0
    for _ in range(n - 1):
        updated = distance.copy()
        for u, v, weight in times:
            updated[v] = min(updated[v], distance[u] + weight)
        distance = updated
    answer = max(distance[1:])
    return -1 if answer == float('inf') else answer

assert baseline([[1, 2, 4], [1, 3, 1], [3, 2, 1]], 3, 1) == 2
assert baseline([[1, 2, 4]], 2, 2) == -1
assert baseline([[1, 2, 0]], 2, 1) == 0

Each of the n − 1 rounds copies the times and scans all E links, so this takes O(n(n + E)) time. With 100 nodes and 6,000 links, that's about 600,000 steps. It uses O(n) extra space.

The bottleneck. Every round rescans every link, even links whose starting node's time hasn't changed.

3. The observation

In the first example, node 1 starts at time 0. Its links give node 3 a time of 1 and node 2 a time of 4. Node 3's time, 1, is the smallest we know. Could a cleverer route reach node 3 sooner? Any other route would first pass through node 2, which already costs 4. Links never cost less than zero, so nothing can beat 1. Node 3's time is final.

That's the idea behind Dijkstra's algorithm. The smallest time among nodes not yet settled is always final. So settle that node, then check only its outgoing links for faster routes. A min-heap gives you the smallest time in O(log n). When a node's time improves, push the new time. Leave the old entry in the heap, and skip it when it comes out.

The answer is the largest of the shortest times, because the signal travels down every link at once. The last node to get it decides when everyone has it.

4. The solution and a trace

from heapq import heappop, heappush

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        """Nodes 1..n, source in range, unique directed links with weights >= 0."""
        graph = [[] for _ in range(n + 1)]
        for u, v, weight in times:
            graph[u].append((v, weight))
        distance = [float('inf')] * (n + 1)
        distance[k] = 0
        settled = [False] * (n + 1)
        pending = [(0, k)]
        while pending:
            arrival, node = heappop(pending)
            if settled[node] or arrival != distance[node]:
                continue
            settled[node] = True  # Its shortest arrival is now final.
            for neighbor, weight in graph[node]:
                candidate = arrival + weight
                if not settled[neighbor] and candidate < distance[neighbor]:
                    distance[neighbor] = candidate
                    heappush(pending, (candidate, neighbor))
        answer = max(distance[1:])
        return -1 if answer == float('inf') else answer

solve = Solution().networkDelayTime
assert solve([[1, 2, 4], [1, 3, 1], [3, 2, 1]], 3, 1) == 2
assert solve([[1, 2, 4]], 2, 2) == -1
assert solve([[1, 2, 0]], 2, 1) == 0

Trace the first example. Times are listed for nodes 1, 2, 3, and the heap is shown in pop order:

5. Why it works

Times are never too small. Every time we record belongs to a real route, so it can't beat the true shortest time.

Settled times are never too big. Suppose we settle node x, but a shorter route to x exists. That route starts among settled nodes and must leave them at some first unsettled node, y. We already checked the link into y, so y's time is at most the length of that route so far. Links cost zero or more, so y's time is at most the shorter route's length, which is less than x's time. Then the heap would have given us y first, not x. So x's time was already the shortest.

The answer is right. Every node reachable from k is eventually settled with its shortest time. Nodes never reached stay at infinity, which gives −1. The largest shortest time is when the last node gets the signal.

6. Cost, edge cases, and failure

Cost. Building the lists takes O(n + E) time. Each node's links are checked once, so there are at most E pushes, each O(log E). That's O(n + E log E) time in total. With 100 nodes and 6,000 links, that's about 80,000 steps, against 600,000 for Bellman–Ford. The lists and the heap, old entries included, take O(n + E) space.

Edge cases. Loops of zero-cost links are safe, because we only push strict improvements. LeetCode always gives at least one link, but with none and n = 1, our function returns 0.

Where it fails. A negative link breaks the "smallest time is final" rule, even without a negative loop. Use Bellman–Ford for negative links:

negative = [[1, 2, 2], [1, 3, 5], [3, 2, -10], [2, 4, 10]]
assert solve(negative, 4, 1) == 12  # Outside contract: settles 2 too early.
assert baseline(negative, 4, 1) == 5  # True arrivals: 0, -5, 5, 5.
assert solve([], 1, 1) == 0

import random
rng = random.Random(743)
for _ in range(700):
    n = rng.randrange(1, 9)
    times = [[u, v, rng.randrange(6)]
             for u in range(1, n + 1) for v in range(1, n + 1)
             if u != v and rng.randrange(4) == 0]
    k = rng.randrange(1, n + 1)
    before = [edge[:] for edge in times]
    assert solve(times, n, k) == baseline(times, n, k)
    assert times == before
assert solve([[i, i + 1, 100] for i in range(1, 100)], 100, 1) == 9900