Network Delay Time

Try to solve the Network Delay Time problem.

We'll cover the following

Statement#

A network of n nodes labeled 11 to nn is provided along with a list of travel times for directed edges represented as times[i]=(xi​, yi, ti​)times[i]=(x_i​, \space y_i, \space t_i​), where xix_i​ is the source node, yiy_i​ is the target node, and tit_i​ is the delay time from the source node to the target node.

Considering we have a starting node, k, we have to determine the minimum time required for all the remaining n−1n - 1 nodes to receive the signal. Return −1-1 if it’s not possible for all n−1n - 1 nodes to receive the signal.

Constraints:

  • 1≤1 \leq k ≤\leq n ≤\leq 100100
  • 1≤1 \leq times.length ≤\leq 60006000
  • times[i].length ==3== 3
  • 1≤x,y≤1 \leq x, y \leq n
  • xx !=!= yy
  • 0≤t≤1000 \leq t \leq 100
  • Unique pairs of (x,y)(x, y), which means that there should be no multiple edges

Examples#

Created with Fabric.js 3.6.6

1 of 3

Created with Fabric.js 3.6.6

2 of 3

Created with Fabric.js 3.6.6

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Network Delay Time

1

What is the minimum time it takes for all the n nodes to receive the signal?

times = [[3, 1, 1], [2, 3, 1], [2, 4, 1]]
n = 4
k = 2

A)

1

B)

2

C)

3

D)

-1

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create an adjacency dictionary to store the information of the nodes and their edges.

Create a visited set to track the nodes that have already been processed and a priority queue to store the nodes and their delay times.

Process the nodes from the priority queue by first visiting the node with the smallest delay time and updating the delay time if necessary.

Add the unvisited neighbors of the processed node to the priority queue with their new delay times.

Return the delay time if all nodes have been processed. Otherwise, return −1.−1.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Input #3
Network Delay Time

Graphs: Introduction

Solution: Network Delay Time