743. Network Delay Time

Option 1

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(list)
        for node1, node2, delay in times:
            graph[node1].append((delay, node2))
                    
        min_heap = [(0, K)]
        dist = {}
        while min_heap:
            elapsed, node = heapq.heappop(min_heap)
            if node in dist:
                continue
            dist[node] = elapsed
            for delay, nei in graph[node]:
                if nei not in dist:
                    heapq.heappush(min_heap, (elapsed+delay, nei))
        
        res = max(dist.values())
        return res if len(dist) == N else -1

Time complexity: E = len(times) is number of edges. O(E) to build graph, O(ElogE) to iterate the heap since every edge could be added to heap. Total time complexity is O(ElogE) = O(E logN^2) = O(ElogN)

Option 2

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(list)
        for node1, node2, delay in times:
            graph[node1].append((delay, node2))
            
        dist = {node: float("inf") for node in range(1, N+1)}
        
        def dfs(node, elapsed):
            if elapsed >= dist[node]:
                return
            
            dist[node] = elapsed
            for time, nei in sorted(graph[node]):
                dfs(nei, elapsed + time)
        
        dfs(K, 0)
        res = max(dist.values())
        return res if res < float("inf") else -1

Time complexity: E = len(times) is number of edges. Suppose there are a groups of edges so sort each group takes O(a x loga). Since xlogx + ylogY <= (x+y) log(x+y), so the total complexity is bounded with O(ElogE). There are N nodes and each node could receive signal from any of the remaining N-1 nodes so each node can be visited N-1 times. Final time complexity is O(N^N + ElogE)
Space complexity: O(E+N) for graph and O(N) for recursion stack so O(E+N) in total.

743. Network Delay Time - cocoder39/coco39_LC GitHub Wiki