Network Delay Time: Dijkstra's Algorithm

You have a network of servers, and you want to know how long it takes a signal to reach every machine. That is LeetCode 743: Network Delay Time, and it is one of the cleanest introductions to Dijkstra's shortest path algorithm you will find on LeetCode. If you have never implemented Dijkstra's from scratch, this problem is the one to start with.

The problem

You are given n nodes labeled 1 to n and a list of directed edges times[i] = [u, v, w], meaning a signal sent from node u reaches node v in w time units. Given a starting node k, return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

In other words: find the shortest path from k to every other node, then return the longest of those shortest paths. If any node is unreachable, the answer is -1.

Source nodeReached nodeUnreached node

The approach

This is a textbook single-source shortest path problem. Dijkstra's algorithm is the right tool because all edge weights are positive.

Here is the plan:

1. Build an adjacency list from the edge list so you can quickly look up neighbors
2. Initialize distances: every node starts at infinity except the source, which starts at 0
3. Use a min-heap: push (0, k) onto the heap, then repeatedly pop the node with the smallest tentative distance
4. Process each node once: when you pop a node, if you have already finalized it, skip it. Otherwise, record its distance and push all its unvisited neighbors with updated distances
5. Return the answer: if all n nodes have been reached, the answer is the maximum distance among them. Otherwise, return -1

The key insight is that the min-heap always gives you the unprocessed node with the smallest distance. Once you pop a node, its distance is final. You never need to revisit it.

import heapq
from collections import defaultdict

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    dist = {}
    heap = [(0, k)]

    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue
        dist[node] = d
        for neighbor, weight in graph[node]:
            if neighbor not in dist:
                heapq.heappush(heap, (d + weight, neighbor))

    return max(dist.values()) if len(dist) == n else -1

The dist dictionary serves double duty: it stores finalized distances and acts as a "visited" set. If a node is already in dist, you skip it when it gets popped from the heap. This avoids the need for a separate visited set.

Step-by-step walkthrough

Let's trace through Dijkstra's algorithm on our example graph with edges [[2,1,1], [2,3,1], [3,4,1]], source k = 2, and n = 4.

Every time we pop from the heap, we finalize a node's distance. The heap ensures we always process the closest unfinalized node first. After processing all reachable nodes, we check whether every node was reached and return the maximum distance.

Complexity analysis

Time: Each edge is relaxed at most once, and each relaxation involves a heap push that costs O(log V). With E edges total, the overall time is O(E log V). Popping from the heap also costs O(log V), and we pop at most V times, adding O(V log V). The dominant term is O(E log V) since E is typically at least V - 1 in a connected graph.

Space: The adjacency list stores all E edges, taking O(V + E). The heap can hold at most E entries in the worst case (one per edge relaxation). The distance dictionary holds at most V entries. Total space is O(V + E).

The building blocks

Dijkstra's shortest path algorithm

Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a graph with non-negative edge weights. It works by greedily expanding the closest unvisited node, using a min-heap to efficiently find that node.

The algorithm is correct because of the greedy choice property: if all weights are non-negative, the shortest path to the closest unfinalized node cannot be improved by going through a farther node first. This is why Dijkstra's does not work with negative weights. If an edge can have a negative weight, a longer path through it might end up shorter, breaking the greedy assumption. For graphs with negative edges, you need Bellman-Ford instead.

When should you use Dijkstra's vs BFS? BFS finds shortest paths when all edges have the same weight (or equivalently, weight 1). It processes nodes in layers, where each layer is one hop farther from the source. Dijkstra's generalizes this to weighted graphs. If the problem gives you unweighted edges, BFS is simpler and runs in O(V + E) without the log factor. If edges have different positive weights, reach for Dijkstra's.

Adjacency list construction

Before you can run any graph algorithm, you need to convert the edge list into an adjacency list. For this problem, the edge list is times[i] = [u, v, w], and you build:

graph = defaultdict(list)
for u, v, w in times:
    graph[u].append((v, w))

This is a directed graph, so you only add the edge in one direction. Each entry in the adjacency list stores both the neighbor node and the edge weight, since Dijkstra's needs to know the cost of traversal.

Edge cases

• Unreachable nodes: If the graph is disconnected and some nodes cannot be reached from k, the algorithm naturally handles this. After the heap is empty, len(dist) will be less than n, so you return -1.
• Single node: n = 1, times = []. The source is the only node, and its distance is 0. max(dist.values()) returns 0.
• Multiple edges between the same pair: The algorithm handles duplicates correctly. If there are two edges from u to v with different weights, both get pushed to the heap, and the shorter one gets processed first. The longer one gets skipped when popped because v is already in dist.
• Self-loops: An edge [u, u, w] gets pushed to the heap but is immediately skipped on pop because u is already finalized.

From understanding to recall

You have seen how Dijkstra's algorithm works on this problem. The logic is clean: build the graph, push the source onto a heap, pop the closest node, relax its neighbors, repeat. But reproducing this under interview pressure is a different challenge. You need to remember to use a dictionary for dist instead of a list (since nodes are 1-indexed), to skip already-finalized nodes, and to check len(dist) == n at the end.

Spaced repetition bridges that gap. You practice writing the heap loop, the neighbor relaxation, and the final check from scratch at increasing intervals. After a few rounds, the pattern becomes automatic. When a shortest-path problem appears in your interview, you do not need to rederive anything. You just write it.

Related posts

• Course Schedule - Graph traversal with topological ordering
• Clone Graph - Graph traversal with BFS
• Number of Islands - Graph search on a grid