Problem statement

https://leetcode.com/problems/network-delay-time/

Solution

Actually, what we asked in this problem is to find maximum among all minimum values between given node and all other nodes. There are two classical ways to do it: first one is dfs with multiple visiting, which woks fine in practice, but it is difficult to estimate complexity.

Another is vanilla Dijkstra algorithm, using heaps.

Complexity

Time complexity is O(E log E) and space complexity is O(N + E).

Code

class Solution:
    def networkDelayTime(self, times, N, K):
        dist = [float('inf')] * (N+1)
        dist[K] = 0
        G = defaultdict(list)
        
        for a, b, w in times:
            G[a].append((b, w))
            
        heap = [(0, K)]

        while heap:
            min_dist, node = heappop(heap)
            for neibh, weight in G[node]:
                cand = min_dist + weight
                if cand < dist[neibh]:
                    dist[neibh] = cand
                    heappush(heap, (cand, neibh))
        
        ans = max(dist[1:])
        return ans if ans != float("inf") else -1