[00:01] hard. Let me prove it. Imagine a network of servers. Each connection has a latency, which is the time a message takes to travel across it. One server propagates through the network until every machine has received it. How long
[00:14] does it take for each server to receive that alert? The alert is not waiting in any line. Rather, it's traveling down every available path at the same time in parallel. So, each server hears it by whichever route reaches it the fastest.
[00:26] time it gets the alert is just the shortest path from the source. But, we care about the slowest path to a server, as the network is only fully alerted once the last server has heard it. So, our answer is the maximum of all of
[00:39] those shortest paths. That insight reframes the whole problem. It is just a shortest path problem in disguise. And trying every path for each server blows smarter. Since all our latencies are positive, we can be greedy. That's where
[00:54] trace through it. We start with the source at distance zero and push it onto a min heap. The heap is the secret sauce here. It always hands us the node with the smallest known distance. So, we can pop that smallest, then look at each of
[01:08] its neighbors. For each one, we simply ask, is going through this node a shorter path than what we already had? If the answer is yes, then we update the distance and push the neighbor back onto the heap. This step is called relaxing
[01:20] the edge. Now, watch this carefully. This is the moment that really matters. There is a direct edge from the source to this server with a cost of five. But, going through the neighbor only costs four. So, Dijkstra silently updates the
[01:32] distance from five to four. The heap pops the cheaper version first, so it always finds the right answer for free. We keep popping and relaxing until the heap is eventually empty, and every node now holds its true shortest distance
[01:45] from the source. The answer is just the maximum of all of those distances. That is exactly the moment when the last server got its alert. The time complexity then is just V plus E log V, where each node lands on the heap at
[01:58] most once. So, anytime you see shortest path with positive weights on the edges, try Dijkstra's with a min heap. Dive even deeper with interactive visualizations at hellointerview.com. The link's in our bio.