Network Delay Time

Patrick Leaton
Published: Sept. 29, 2021, 11:23 p.m.
Problem Description

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 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:

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

Example 2:

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

Example 3:

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

 

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.)

 

The description was taken from https://leetcode.com/problems/network-delay-time/.

Problem Solution

#O(E(log(E))) Time, O(N) Space
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        distances = {}
        for i in range(1, n+1):
            distances[i] = float("inf")
        distances[k] = 0

        adjacency = collections.defaultdict(list)
        for source, dest, time in times:
            adjacency[source].append((dest, time))
       
        heap = [(0, k)]
        while heap:
            delay, node = heapq.heappop(heap)
            for neighbor, curr_delay in adjacency[node]:
                delay_time = curr_delay + delay
                if delay_time < distances[neighbor]:
                    distances[neighbor] = delay_time
                    heapq.heappush(heap, (distances[neighbor], neighbor))
       
        if max(distances.values()) != float("inf"):
            return max(distances.values())
        else:
            return -1
 

Problem Explanation

The problem gives us a graph with positive-weighted edges and asks us to return the time it takes for each node to receive a signal, which is basically asking the shortest path from the source node to all of the other nodes.

For questions like this, Dijkstra's algorithm is typically a good approach.

Similar to traditional implementations, we will create our distances list, convert the input to an adjacency list to track the delay time from each node to its neighbors, then we will push the source node onto a heap and while the heap still has nodes, we will continuously check if any neighbor edge has a shorter path capable than what we have written down for it, updating it if that is the case.

Once we have finished, the shortest time it takes for the signal to reach each node will be the longest path in the distances list.  If that value is infinity by the time we finish, then there wasn't a path from the source node to the target node.

Let's start by creating our distances list, here we are using a hashmap because arrays begin at zero and we won't have to worry about subtracting nodes by one to get their distance indices.

We will mark each initial shortest distance as infinity with the exception of the source node.

        distances = {}
        for i in range(1, n+1):
            distances[i] = float("inf")
        distances[k] = 0

 

Next, we will make our adjacency list.

Within it, we will have the mapping between each node and its neighbor, as well as the time it takes to travel across that edge.

        for source, dest, time in times:
            adjacency[source].append((dest, time))

 

Now, we will initialize our heap with the zero distance it takes to get to the source node and the source node.

        heap = [(0, k)]

 

While we have nodes on our heap, we have edges we need to relax.

        while heap:

 

What we will do is pop the node with the shortest delay time it takes to arrive at it off of the heap.

Then, we will observe the current delay to this node's neighbors by calculating the time it takes to arrive at the node and adding that to the time it takes to arrive at the neighbor.

            delay, node = heapq.heappop(heap)
            for neighbor, curr_delay in adjacency[node]:
                delay_time = curr_delay + delay

 

If that delay time is shorter than the shortest path distance we have saved for this neighbor, we will update the distance with the shorter time to relax the edge to this neighbor, then push the neighbor onto the heap so that we can try to relax the edges to its neighbors now that we have a shorter path to it.

                if delay_time < distances[neighbor]:
                    distances[neighbor] = delay_time
                    heapq.heappush(heap, (distances[neighbor], neighbor))

 

As mentioned previously, once we have finished, the shortest time it takes for the signal to reach each node will be the longest path in the distances list.  If that value is infinity by the time we finish, then there wasn't a path from the source node to the target node.

Otherwise, we will return that value.

        if max(distances.values()) != float("inf"):
            return max(distances.values())
        else:
            return -1