Solution: Network Delay Time

Statement#

A network of n nodes labeled $1$ to $n$ is provided along with a list of travel times for directed edges represented as $times[i]=(x_i​, \space y_i​, \space t_i​)$, where $x_i$​ is the source node, $y_i$​ is the target node, and $t_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 for n - 1 nodes to receive the signal. Return $-1$ if it is not possible for all n - 1 nodes to receive the signal.

Constraints:

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

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach is to use a simple brute force method. The algorithm would start by initializing all distances (time to travel from source to target node) to infinity, representing disconnection between the two nodes. Then, each node would use a nested loop to go through all other nodes and update their distances using the given travel times. If there is no connection between a source and a target node, its distance will not be updated. After updating all distances, the algorithm would find the maximum distance among all nodes, representing the minimum time it takes for all nodes to receive the signal. If a node that cannot be reached from node k exists, it means the distance is infinity, and it will return -1.

This approach has a time complexity of $O(n^2)$, where $n$ is the number of nodes in the graph.

Optimized approach using Dijkstra’s algorithm#

Dijkstra’s algorithm is widely used for finding the shortest path between nodes in a graph. This makes it ideal for finding the minimum delay time in a network.

We will use an adjacency dictionary. The source node will be used as key, and the value is a list of tuples that have the destination node and the time for the signal to travel from source to destination node. A priority queue is initialized with time initialized to $0$ and starting node k as a tuple. The priority queue ensures that the node with the minimum time is retrieved in each iteration. We will iterate over the priority queue to traverse the nodes in the network. If the node is not visited, the time of the retrieved node is compared to the current delay time and updated accordingly. The neighbors of the retrieved node are found using the adjacency dictionary and are added to the queue with their times updated by adding the delay time from the retrieved node.

Finally, if all the network nodes have been visited, we will return the computed time. Otherwise, $-1$ will be returned.

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to the Just the code section.

Step-by-step solution construction#

Let’s start our solution by constructing the adjacency dictionary. The source node will be the key, whereas the destination node and the corresponding time required to travel from the source to the destinate node are going to be part of the value list. The source nodes not present in the adjacency dictionary will return an empty list.

In the following code, we are creating a priority queue in line 13 and adding the source node with a delay time of $0$ in line 15. The priority queue stores the delay time of each node as the first element of each tuple and the node as the second element (time, node). This queue keeps track of which node needs to be processed next, with the node having the minimum delay time being processed first.

Additionally, we also initialize an empty set called visited in line 16, which will be used to track of nodes that have already been processed. The delays variable is initialized to $0$ and will be used to keep track of the delay time among all the nodes in the network.

We will start a loop that continues until the pq is not empty (lines 19–41). In the loop, deqeue the tuple with the minimum delay time. Then we will check if this node has already been processed, i.e., it is present in the visited set; see line 27.

If it has not been processed, the algorithm adds the node to the visited set (line 30) and updates the delays value (line 31) if the node’s delay time is greater than the current delays value.

Next, the neighbors of the current node are retrieved from the adjacency dictionary (line 32), and for each unvisited neighbor, its delay time (line 40) is computed by adding the delay time of the current node and the delay time between the current node and the neighbor. These neighbors are then added to the pq (line 41) so they can be processed in the next iteration of the while loop.

Finally, we will check if the number of nodes visited equals the total number of nodes, n (line 44). If TRUE, we will return the delay time stored in the delays (line 45); otherwise, return $-1$. This step ensures that the algorithm has processed all the nodes. If all nodes have not been processed, it indicates that some nodes in the network are not reachable from the source node.

Just the code#

Here’s the complete solution to this problem:

Solution summary#

The algorithm can be summarized in the following steps:

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

2. Use a priority queue to store the nodes and their delay times. Initialize the queue with the source node and a delay time of 0.

3. Use a visited set to track the nodes that have already been processed.

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

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

6. Return the delay time if all nodes have been processed. Otherwise, return $-1$.

Time complexity#

This algorithm takes $O(E\log N)$, where $E$ is the total number of edges, and $N$ is the number of nodes in the network since push and pop operations on the priority queue take $O(\log N)$ time.

Space complexity#

The space complexity is $O(N+E)$, where $N$ is the number of nodes in the graph, and $E$ is the number of edges required by the adjacency dictionary and priority queue.