Solution: Network Delay Time

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Network Delay Time

Table of Contents

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

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

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

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 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Solution

To solve this problem, we will use the Bellman-Ford algorithm. This algorithm is well-suited for this task because it can handle graphs with negative weights and can find the shortest paths from a single source node to all other nodes. The Bellman-Ford algorithm works by iterating through all the edges multiple times, updating the shortest known distances to each node. If we find a shorter path to any node, we update our distance estimate for that node.

This approach is effective because it guarantees finding the shortest path in a graph with non-negative weights in O(n * e) time complexity, where n is the number of nodes and e is the number of edges. This efficiency is sufficient for the problem constraints.

Step-by-step Algorithm

Initialization:
- Create a distance array dist of size n + 1 and initialize all values to infinity.
- Set dist[k] = 0 since the distance from the start node k to itself is 0.
Relaxation:
- Repeat the following process for n - 1 times (Bellman-Ford algorithm iterates n-1 times):
 - For each edge (u, v, w) in times:
 - If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
 - This step checks if the current path to node v through node u is shorter than the previously known path to v.
Traverse dist array to Find the Maximum Distance:
- If any node is still at infinity (dist[i] == Integer.MAX_VALUE or dist[i] == float('inf')), return -1.
- Otherwise, find the maximum value in the distance array dist from index 1 to n.
- Return this maximum value, which represents the time it takes for the signal to reach the farthest node.

Algorithm Walkthrough

Given:

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

Initialization

Initialize dist as [inf, 0, inf, inf, inf]. (Node k is 1, so dist[1] = 0).

Iteration 1

Relax edge (1, 2, 3):
- dist[1] + 3 < dist[2] -> 0 + 3 < inf -> dist[2] = 3
- dist becomes [inf, 0, 3, inf, inf]
Relax edge (1, 3, 4):
- dist[1] + 4 < dist[3] -> 0 + 4 < inf -> dist[3] = 4
- dist becomes [inf, 0, 3, 4, inf]
Relax edge (2, 4, 5):
- dist[2] + 5 < dist[4] -> 3 + 5 < inf -> dist[4] = 8
- dist becomes [inf, 0, 3, 4, 8]
Relax edge (3, 4, 1):
- dist[3] + 1 < dist[4] -> 4 + 1 < 8 -> dist[4] = 5
- dist becomes [inf, 0, 3, 4, 5]

Iteration 2

Relax edge (1, 2, 3):
- dist[1] + 3 < dist[2] -> 0 + 3 < 3 -> No change
- dist remains [inf, 0, 3, 4, 5]
Relax edge (1, 3, 4):
- dist[1] + 4 < dist[3] -> 0 + 4 < 4 -> No change
- dist remains [inf, 0, 3, 4, 5]
Relax edge (2, 4, 5):
- dist[2] + 5 < dist[4] -> 3 + 5 < 5 -> No change
- dist remains [inf, 0, 3, 4, 5]
Relax edge (3, 4, 1):
- dist[3] + 1 < dist[4] -> 4 + 1 < 5 -> No change
- dist remains [inf, 0, 3, 4, 5]

Iteration 3

Relax edge (1, 2, 3):
- dist[1] + 3 < dist[2] -> 0 + 3 < 3 -> No change
- dist remains [inf, 0, 3, 4, 5]
Relax edge (1, 3, 4):
- dist[1] + 4 < dist[3] -> 0 + 4 < 4 -> No change
- dist remains [inf, 0, 3, 4, 5]
Relax edge (2, 4, 5):
- dist[2] + 5 < dist[4] -> 3 + 5 < 5 -> No change
- dist remains [inf, 0, 3, 4, 5]
Relax edge (3, 4, 1):
- dist[3] + 1 < dist[4] -> 4 + 1 < 5 -> No change
- dist remains [inf, 0, 3, 4, 5]

Final Check and Result

After all iterations, the maximum distance in dist (ignoring dist[0]) is 5.
Return 5 as the minimum time for all nodes to receive the signal.

Code

Python3

. . . .

Complexity Analysis

Time Complexity

The time complexity of the Bellman-Ford algorithm is $O(V \times E)$ , where (V) is the number of vertices (nodes) and (E) is the number of edges. This is because the algorithm iterates over all edges up to (V-1) times, performing a relaxation step for each edge.

Initialization: Setting up the distance array takes $O(V)$ .
Edge Relaxation: Each iteration over all edges takes $(E)$ , and we repeat this (V-1) times.

Therefore, the total time complexity is $O(V + V \times E)$ , which simplifies to $O(V \times E)$ .

Space Complexity

The space complexity is $O(V)$ because we need to store the distance to each node in an array. We also use a constant amount of extra space for variables.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible