Graphs
Network Delay Time
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:
4
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.
Explanation
Understanding the Problem
Choosing the Right Algorithm
The observation
Handling Unreachable Servers
How Dijkstra Works
Solution
Why Not BFS?
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Unlock Premium Coding Content
On This Page