---
title: 'Network Delay Time | Dijkstra''s Algorithm'
source: 'https://youtube.com/watch?v=vQN6FvYZBss'
video_id: 'vQN6FvYZBss'
date: 2026-08-04
duration_sec: 130
---

# Network Delay Time | Dijkstra's Algorithm

> Source: [Network Delay Time | Dijkstra's Algorithm](https://youtube.com/watch?v=vQN6FvYZBss)

## Summary

This video explains how to solve the 'Network Delay Time' problem using Dijkstra's algorithm with a min-heap. It reframes the problem as finding the maximum of all shortest paths from a source node, then walks through the algorithm's mechanics, including edge relaxation and complexity analysis.

### Key Points

- **Problem Setup** [00:01] — The problem involves a network of servers with latencies on connections. An alert propagates in parallel along all paths, so each server receives it via the fastest route (shortest path). The network is fully alerted when the last server receives it, so the answer is the maximum of all shortest paths.
- **Reframing as Shortest Path** [00:39] — The problem is a shortest path problem in disguise. Since all latencies are positive, a greedy approach works, leading to Dijkstra's algorithm.
- **Min-Heap as Secret Sauce** [00:54] — The min-heap always provides the node with the smallest known distance. Start with the source at distance zero, push it onto the heap, then repeatedly pop the smallest and relax its neighbors.
- **Edge Relaxation** [01:20] — For each neighbor, check if going through the current node yields a shorter path. If yes, update the distance and push the neighbor back onto the heap. This is called relaxing the edge.
- **Key Insight: Silent Update** [01:32] — Even if there's a direct edge with cost 5, going through a neighbor might cost only 4. Dijkstra updates the distance from 5 to 4, and the heap pops the cheaper version first, ensuring correctness.
- **Final Answer and Complexity** [01:45] — After the heap is empty, each node holds its true shortest distance. The answer is the maximum of those distances. Time complexity is O(V + E log V), as each node lands on the heap at most once.

### Conclusion

The video demonstrates that the Network Delay Time problem is essentially a shortest path problem solvable with Dijkstra's algorithm using a min-heap. The key takeaway is to recognize such problems and apply the algorithm for efficient solutions.

## Transcript

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
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.
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
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
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
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
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
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
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
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.