# Tree - Network Delay Time

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

Dijkstra’s Algorithm (Graph), BFS, Min-Heap

## Problem

You are given a network of `n`

nodes, labeled from `1`

to `n`

. You are also given `times`

, a list of travel times as directed edges `times[i] = (ui, vi, wi)`

, where `ui`

is the source node, `vi`

is the target node, and `wi`

is the time it takes for a signal to travel from source to target.

We will send a signal from a given node `k`

. Return *the minimum time it takes for all the*

`n`

*nodes to receive the signal*. If it is impossible for all the

`n`

nodes to receive the signal, return `-1`

.**Example 1:**

1
2

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

## Solution

This is the classic **Dijkstra’s Algorithm**. If you know how to solve it then there is no additional explanation is required.

### High Level Explanation

- Traverse the graph based on current smallest weights using
**min heap**. - Do not visit a node if its already visited using the
**visit set**. - Add
**cumulative****weight**as the key to the min heap.

The first thing we will do it create the edge list (**Adjacency Map**). This part is very common for most of the graph problem. Loop through each element in `times`

array and append the connected nodes with the edge weights.

1
2
3
4

def network_delay_time(times,n,k):
edges = collections.defaultdict(list)
for u, v, w in times:
edges[u].append((v,w))

We need to start from the provided node `k`

. Add that manually to the min-heap with weight set to `0`

as this will be the starting node.

The

weightis the first element in thetuple, hence the heap will besortedbased on the weight by default.This is one of the most important step

1

min_heap = [(0,k)]

Create a `visited`

`set`

for avoiding duplicate paths and `distance`

for tracking the last visited node.

1
2

visited = set()
distance = 0

Next, keep looping until the `min_heap`

is not empty so that we can traverse across the entire directed graph using `BFS`

. During every visit, pop the top element from the `min_heap`

which is the node with min `weight`

.

1
2

while min_heap:
parent_weight,parent_node = heapq.heappop(min_heap)

Here is a sample of how the logic is going to workout. We will start from node `1`

and traverse through the graph. Notice, the node `2`

can be reached in two different ways, however `(4,2)`

entry will be skipped as `(3,2)`

will be popped before it and the node `2`

will be marked as `visited`

in the `set()`

.

If the popped node is already in the `visited`

`set`

we won’t do anything. Any node with alternative larger cumulative weight will **not be processed** automatically using the `visited`

`set()`

.

1
2

if parent_node in visited:
continue

Otherwise add it to the `visited`

`set`

and save the `parent_weight`

. The assumption here is the last visited node will always be farthest away from node `k`

as we are always popping the min weight from the `min_heap.`

This `distance`

will be returned at the end.

This is the extra step added on top of basic

`Dijkstra's Algorithm`

with BFS.

This is one of the

most important stepthat you might miss to understand. The`distance`

will be returned at the end, hence the`parent_weight`

must be assigned to itonly afterthe validation that the`parent_node`

is not in the`visited`

set. This way we will know`parent_node`

must be part of the path. Adding this before the previous`if`

will cause issues as`visited`

node’s weights will be returned, which is not desired.

1
2

visited.add(parent_node)
distance = parent_weight

Now add all the nodes in the `min_heap`

which can be reached from the `parent_node`

.

The last line is the most important where we are appending the

`parent_weight`

with the`child_weight`

to get thecumulative weightto reach from node`k`

to the current`child_node`

.

1
2
3

for child_node, child_weight in edges[parent_node]:
if child_node not in visited:
heapq.heappush(min_heap, (parent_weight+child_weight,child_node))

Finally, return the `distance`

only if we have visited all the `n`

nodes, else return `-1`

.

1

return distance if len(visited) ==n else -1

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def network_delay_time(times, n, k):
edges = collections.defaultdict(list)
for u, v, w in times:
edges[u].append((v, w))
visited = set()
distance = 0
min_heap = [(0, k)]
while min_heap:
parent_weight, parent_node = heapq.heappop(min_heap)
if parent_node in visited:
continue
distance = parent_weight
visited.add(parent_node)
for child_node, child_weight in edges[parent_node]:
if child_node not in visited:
heapq.heappush(
min_heap, (parent_weight+child_weight, child_node))
return distance if len(visited) == n else -1