A signal starts at node k and travels along directed, weighted edges. Return the time until every node has received the signal, or minus 1 if some node never does.
DSA Animator › DSA Revision › Graph › Network Delay Time
Remember: the first time Dijkstra pops a node, its distance is final. Skip stale heap entries instead of deleting them. The video solves Network Delay Time (LeetCode 743, Medium) with the Dijkstra pattern from the Graph topic, and you can replay every step in the interactive Network Delay Time animation.
A signal starts at node k and travels along directed, weighted edges. Return the time until every node has received the signal, or minus 1 if some node never does.
For edges 2 to 1 with time 1, 2 to 3 with time 1, 3 to 4 with time 1, and 1 to 4 with time 3, starting at 2, the answer is 2.
Trying every path to every node is exponential. Since all times are positive, the shortest arrival times can be fixed one node at a time.
This is a single source shortest path problem, so use Dijkstra’s algorithm. Keep a min heap of pairs: the time so far, and the node. Pop the node with the smallest time, and that time is final, because every other route is already at least as slow. Then push its neighbours with the time plus the edge weight. The answer is the largest final time, if every node got one.
Start with node 2 at time 0. Pop 2, and push node 1 at time 1 and node 3 at time 1. Pop node 1 at time 1, and push node 4 at time 1 plus 3, which is 4. Pop node 3 at time 1, and push node 4 at time 2. Pop node 4 at time 2, which is final, and the older entry at time 4 is skipped later. Every node is reached, and the largest time is 2.
In code, build an adjacency list of pairs, neighbour and weight. Use a priority queue ordered by time, starting with k at time 0. Poll an entry, and skip it if the node already has a final time. Otherwise record the time, and offer every neighbour with the added weight. It's O of e log v.
Remember: the first time Dijkstra pops a node, its distance is final. Skip stale heap entries instead of deleting them.