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.
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 = 3k = 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.
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 Key Insight
The problem asks: how long 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
Consider the first example: 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 some 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.
Visualization
Python
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 / 16
Dijkstra finding shortest paths to all servers
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O((V + E) log V) where V is the number of servers and E is the number of connections. Each node is added to the heap at most once (O(V log V)), and each edge might trigger a heap update (O(E log V)).
Space Complexity: O(V + E) for the adjacency list (O(E)), distance map (O(V)), and priority queue (O(V)).
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).
