Graphs

Network Delay Time

medium

DESCRIPTION (inspired by Leetcode.com)

A distributed system has n servers labeled 1 to n. The servers communicate through directed connections, where each connection [from, to, latency] means server from can send a message to server to with the given latency (in milliseconds).

When server k broadcasts an alert, it propagates through the network along all available paths. Return the minimum time required for every server to receive the alert. If some servers are unreachable from k, return -1.

Example 1:

Input:

connections = [[1,2,3], [1,3,5], [2,3,1]]
n = 3
k = 1

Output:

Explanation: There are two paths to server 3: the direct path 1→3 takes 5ms, but the path 1→2→3 takes only 3+1=4ms. The last server to receive the alert determines the answer.

Example 2:

Input:

connections = [[1,2,2], [3,2,1]]
n = 3
k = 1

Output:

-1

Explanation: The edge [3,2,1] points from server 3 to server 2, not the other way around. Server 1 can reach server 2, but there's no path from server 1 to server 3.

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

Explanation

Understanding the Problem

We have a network of servers that communicate through directed connections with varying latencies. When server k broadcasts an alert, it propagates through the network along all available paths simultaneously.

A server receives the alert via whichever path reaches it first (the shortest path). Our task: find the time until every server has received the alert. If some server is unreachable, return -1.

Choosing the Right Algorithm

Before diving into implementation, let's think about which shortest path algorithm fits this problem. If you've read the Shortest Path Algorithms Overview, you know the decision comes down to the edge weights:

Edge Weights	Algorithm	Time Complexity
Unweighted (all = 1)	BFS	O(V + E)
Non-negative	Dijkstra ✓	O((V + E) log V)
Negative allowed	Bellman-Ford	O(V · E)

In this problem:

All latencies are positive (given in constraints) → Dijkstra works
We need single-source shortest paths (from k to all nodes) → Dijkstra is ideal
If we needed all-pairs shortest paths, we'd consider Floyd-Warshall, but that's overkill here

The observation

The problem asks us how long will it take until every server has received the alert?

Since the alert travels through all paths simultaneously, each server receives it via its shortest path from the source. But we need to wait for the last server to receive it. That means:

Run Dijkstra to find the shortest path from k to every server
The answer is the maximum of all these shortest paths
If any server is unreachable (distance = ∞), return -1

Looking back at the first example we are reminded that there's a direct path 1→3 (5ms) and an indirect path 1→2→3 (3+1=4ms). Dijkstra finds the faster 4ms route.

Two paths to server 3: the direct path costs 5ms, but going via server 2 costs only 4ms.

Handling Unreachable Servers

Not all servers may be reachable from the source. The direction of edges matters: [u, v, w] means u→v, not bidirectional.

If the source cannot reach a server, we return -1. In the second example, server 1 can reach server 2, but the only edge involving server 3 points from 3 to 2—not the reverse.

Server 3 is unreachable from source 1 (edge goes 3→2, not 2→3). Return -1.

How Dijkstra Works

Dijkstra's algorithm greedily expands from the node with the smallest known distance. Because all edges are non-negative, once we process a node, we've found its shortest path.

This problem pattern appears frequently: "Find the shortest X from source to all nodes, then compute some aggregate (max, sum, count reachable)."

Solution

The solution is a direct application of Dijkstra's algorithm:

Build the adjacency list from the connections
Run Dijkstra from server k using a min-heap
Check reachability: if we didn't visit all n servers, return -1
Return max distance: the time for the last server to receive the alert

Watch Dijkstra explore the network. Notice how the min-heap always pops the smallest distance, and how distances update as shorter paths are discovered. Try different inputs to see how the algorithm handles various graph structures.

Try these examples:

Visualization


def network_delay_time(times, n, k):
    # Build adjacency list
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    # Dijkstra's algorithm
    distances = {k: 0}
    heap = [(0, k)]
    
    while heap:
        dist, node = heappop(heap)
        
        if dist > distances.get(node, float('inf')):
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances.get(neighbor, float('inf')):
                distances[neighbor] = new_dist
                heappush(heap, (new_dist, neighbor))
    
    # All nodes must be reachable
    if len(distances) != n:
        return -1
    return max(distances.values())

Network Delay Time - Dijkstra's Algorithm

0 / 20

Dijkstra finding shortest paths to all servers

What is the time complexity of this solution?

O(4ⁿ)

O((V + E) log V)

O(4^L)

O(V + E)

Why Not BFS?

BFS only finds shortest paths when all edges have equal weight. In this problem, latencies vary, so we need Dijkstra's greedy approach with a priority queue. If all edges were weight 1, BFS would be simpler and faster at O(V + E).

Mark as read

Next: Cheapest Flights Within K Stops