Leetcode 743. Network Delay Time

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.

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

This question can be solved simply via Dijkstra’s algorithm. However, it could not work for any graph that has negative weight. If the graph has negative weight, it’s better to choose Bellman-Ford algorithm.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = {}

        # We need to build up relationship between each node and n is starting from 1
        for index in range(n):
            graph[index+1] = []

        # Go through each node and add connected node and time cost into the list
        for node in times:
            graph[node[0]].append((node[2], node[1]))

        shortest = {}
        # Set start entry
        minHeap = [(0, k)]

        while minHeap:
            # Using heap to pull out the current min time cost node
            weight, dest = heapq.heappop(minHeap)

            # If the node is already visited, then skip it
            if dest in shortest:
                continue

            # Update the lowest time cost to the shortest map
            shortest[dest] = weight
            related_nodes = graph[dest]
            # Go through other nodes which has been visited
            for next_weight, next_dest in graph[dest]:
                if next_dest not in shortest:
                    # Update time cost, but add up the min cost from previous node to this node
                    heapq.heappush(minHeap, (next_weight+weight, next_dest))

        # Find out the min cost to every node and detect which node is not reachable.
        max_time = 0
        for i in range(n):
            index = i + 1
            if index not in shortest:
                return -1
            elif shortest[index] > max_time:
                max_time = shortest[index]
        
        return max_time