0733. Network Delay Time

0733. Network Delay Time#

Related Problem:

Problem#

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

Examples#

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

Analysis#

  • Shortest Path Problem using Dijkstra’s algorithm

Solution#

# why the following code is wrong? seems cannot deal wtih the case where there are multiple paths between two nodes
# Dijkstra's algorithm do not need to use visited set, because the distance is always the shortest distance from the source node to the current node
def networkDelayTime(times, n, k):

    def buildGraph(times):
        graph = {}
        weights = {}
        for i in range(1, n+1):
            graph[i] = []
        for u, v, w in times:
            graph[u].append(v)
            weights[(u,v)] = w
        return graph, weights
    # initialize a visited set
    visited = set()
    # initialize a distance dict
    distance = {node: float('inf') for node in range(1, n+1)}
    distance[k] = 0
    # build graph
    graph, weights = buildGraph(times)
    # initialize a queue with distance to source node as key and node as value
    queue = [(distance[k], k)]
    # loop until queue is empty
    while queue:
        # pop the node with the shortest distance to source node
        dist, node = queue.pop()
        # if the node is already visited, skip
        visited.add(node)
        # update the distance to the neighbors of the node
        for neighbor in graph[node]:
            # enqueue the neighbor if it is not visited
            if neighbor not in visited:
                queue.append((dist + weights[(node, neighbor)], neighbor))
            # update the distance to the neighbor if the distance to the neighbor is larger than the distance to the node plus the weight of the edge
            distance[neighbor] = min(distance[neighbor], dist + weights[(node, neighbor)])        
    # return the maximum distance
    maxDist = max(distance.values())
    
    return maxDist if maxDist != float('inf') else -1

# test
# 2 
times = [[2,1,1],[2,3,1],[3,4,1]]
n = 4
k = 2
print(networkDelayTime(times, n, k))

# 1
times = [[1,2,1]]
n = 2
k = 1
print(networkDelayTime(times, n, k))

# -1 
times = [[1,2,1]]
n = 2
k = 2
print(networkDelayTime(times, n, k))

# 3
times = [[1,2,1],[2,3,2],[1,3,4]]
n = 3
k = 1
print(networkDelayTime(times, n, k))

# 59
times = [[4,2,76],[1,3,79],[3,1,81],[4,3,30],[2,1,47],[1,5,61],[1,4,99],[3,4,68],[3,5,46],[4,1,6],[5,4,7],[5,3,44],[4,5,19],[2,3,13],[3,2,18],[1,2,0],[5,1,25],[2,5,58],[2,4,77],[5,2,74]]
n = 5
k = 3
print(networkDelayTime(times, n, k))

2
1
-1
3
65

The above code is not correct when the graph is bidirectional, such as a communication network, because visited set avoids multiple visiting of the same node, which is needed in a bidirectional graph though.

What’s more, typical Dijkstra’s algorithm do not use visited as it is not necessary.

def networkDelayTime(times, n, k):

    def buildGraph(times):
        graph = {}
        weights = {}
        for i in range(1, n+1):
            graph[i] = []
        for u, v, w in times:
            graph[u].append(v)
            weights[(u,v)] = w
        return graph, weights

    # initialize a distance dict
    distance = {node: float('inf') for node in range(1, n+1)}
    distance[k] = 0
    # build graph
    graph, weights = buildGraph(times)
    # initialize a queue with distance to source node as key and node as value
    queue = [(distance[k], k)]
    # loop until queue is empty
    while queue:
        # pop the node with the shortest distance to source node
        dist, node = queue.pop()

        # update the distance to the neighbors of the node
        for neighbor in graph[node]:
            # distance to neighbor
            distToNeighbor = dist + weights[(node, neighbor)]
            # if the recorded distance to neighbor is larger than the distance to the node plus the weight of the edge
            if distance[neighbor] > distToNeighbor:
                # update distance table and enqueue the neighbor
                distance[neighbor] = distToNeighbor
                queue.append((distance[neighbor], neighbor))
      
    # return the maximum distance
    maxDist = max(distance.values())
    
    return maxDist if maxDist != float('inf') else -1

# test
# 2 
times = [[2,1,1],[2,3,1],[3,4,1]]
n = 4
k = 2
print(networkDelayTime(times, n, k))

# 1
times = [[1,2,1]]
n = 2
k = 1
print(networkDelayTime(times, n, k))

# -1 
times = [[1,2,1]]
n = 2
k = 2
print(networkDelayTime(times, n, k))

# 3
times = [[1,2,1],[2,3,2],[1,3,4]]
n = 3
k = 1
print(networkDelayTime(times, n, k))

# 59
times = [[4,2,76],[1,3,79],[3,1,81],[4,3,30],[2,1,47],[1,5,61],[1,4,99],[3,4,68],[3,5,46],[4,1,6],[5,4,7],[5,3,44],[4,5,19],[2,3,13],[3,2,18],[1,2,0],[5,1,25],[2,5,58],[2,4,77],[5,2,74]]
n = 5
k = 3
print(networkDelayTime(times, n, k))

2
1
-1
3
59
Contents