Q88: Network Delay Time (Dijkstra’s Algorithm). - DSA Patterns (Multi-Lang)

In Simple Words: Dijkstra's Shortest Path with Min-Heap. Store (cost, node). Pop node with minimal cumulative latency, relax edges to neighbors if new travel time is strictly shorter. Answer is max(dist.values()).

Time: $O((V + E) \log V)$ | Space: $O(V + E)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

import heapq
from collections import defaultdict

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    adj = defaultdict(list)
    for u, v, w in times: adj[u].append((v, w))
    min_heap = [(0, k)]
    visit = {}
    while min_heap:
        w1, n1 = heapq.heappop(min_heap)
        if n1 in visit: continue
        visit[n1] = w1
        for n2, w2 in adj[n1]:
            if n2 not in visit:
                heapq.heappush(min_heap, (w1 + w2, n2))
    return max(visit.values()) if len(visit) == n else -1