You are given a network of n nodes labeled 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u, v, w) where u is the source, v is the target, and w is the time. We send a signal from node k. Return the minimum time for all n nodes to receive the signal. If impossible, return -1.
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22times = [[1,2,1]], n = 2, k = 11times = [[1,2,1]], n = 2, k = 2-1Greedy: always process closest unvisited node. Relaxation: if dist[u]+w<dist[v], update. Max dist = time for last node to receive signal.
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.
The first time Dijkstra pops a node, its distance is final. Skip stale heap entries instead of deleting them.
Run the animation above on your own input, or watch the 1:58 video explanation of Network Delay Time with a dry run and Java code.