How do you compute the time it takes for a signal to reach every node in a network?
You run Dijkstra's algorithm and the answer is the biggest distance that it found, because that is the time for the signal to reach the last node.
import heapq
def network_delay_time(n, times, source):
adjacency = {node: [] for node in range(n)}
for u, v, weight in times:
adjacency[u].append((v, weight))
distance = {source: 0}
heap = [(0, source)]
while heap:
current, node = heapq.heappop(heap)
if current > distance.get(node, float("inf")):
continue
for neighbour, weight in adjacency[node]:
new_distance = current + weight
if new_distance < distance.get(neighbour, float("inf")):
distance[neighbour] = new_distance
heapq.heappush(heap, (new_distance, neighbour))
if len(distance) != n:
return -1
return max(distance.values())
So how does it work? The signal starts at the source at time zero and it travels along the edges. The time it takes to reach a node is the sum of the weights on the route, so this is a shortest path problem and Dijkstra is the right tool.
And the answer is the biggest of the distances. The signal reaches every node at the same time as it reaches the last one, because it spreads out at the same time along every route. So the time for the whole network is the time for the last node to be reached.
the times the distances from node 0
----------------- -------------------------
0 to 1 costs 1 node 0 is 0
0 to 2 costs 4 node 1 is 1
1 to 2 costs 2 node 2 is 3, through node 1
the answer is 3
And the answer is minus one when some node cannot be reached at all. The check if len(distance) != n catches that, because the distance dictionary only holds the nodes that were reached.
And there is a detail worth knowing about. The signal does not stop when it reaches one node, it keeps spreading, so a node that is far away in terms of the number of hops but close in time is still reached early. That is why you need the shortest path and not just any path.
And the complexity is O of n plus m times the log of n for the time and O of n plus m for the space.
So the rule to remember is this. The network delay is the biggest shortest path distance from the source.
The last question in this topic shows the matrix version.