Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Network Delay Time (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

You are given a network of n nodes labeled from 1 to n. You also have a list called times, where each element is a tuple (u, v, w) representing a directed edge from node u to node v with a travel time w.

Determine the minimum time it takes for a signal sent from a given starting node k to reach all other nodes in the network. If it is not possible for the signal to reach all nodes, return -1.

Examples

Example 1:

  • Input: times = [[1, 2, 3], [1, 3, 4], [2, 4, 5], [3, 4, 1]], n = 4, k = 1
  • Expected Output: 5
Image
  • Justification:
    • The fastest route to node 4 from node 1 is via node 3, taking a total of 5 units. Node 2 is reached in 3 units. The maximum time from k to any node is 5.

Example 2:

  • Input: times = [[1, 2, 4], [1, 3, 2], [2, 3, 1], [3, 4, 1]], n = 4, k = 1
  • Expected Output: 4
Image
  • Justification:
    • From node 1, it takes 4 units of time to reach node 2.
    • It takes 2 units of time to reach node 3, and from node 3 it takes 1 unit of time to reach node 4, making the total time 3.
    • So, it takes minimum 4 units of time to reach to all nodes.

Example 3:

  • Input: times = [[1, 2, 1], [2, 3, 2], [3, 4, 3], [4, 5, 4]], n = 5, k = 1
  • Expected Output: 10
Image
  • Justification:
    • The signal will take 1 unit to travel from 1 to 2, 2 units from 2 to 3, 3 units from 3 to 4, and 4 units from 4 to 5. Summing these gives 10.

Constraints:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= u<sub>i</sub>, v<sub>i</sub> <= n
  • u<sub>i</sub> != v<sub>i</sub>
  • 0 <= w<sub>i</sub> <= 100
  • All the pairs (u<sub>i</sub>, v<sub>i</sub>) are unique. (i.e., no multiple edges.)

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible