Core Insight Improve a node’s known cost only when a newly discovered path is genuinely better.
Common Pitfall Discard stale priority-queue entries instead of expanding them a second time.
Description
Find time for all nodes to receive a signal (Dijkstra).
Constraints
- Time Complexity:
O((V+E) log V) - Space Complexity:
O(V+E)
Tags
dfsbfsgraphheapshortest-path
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize distances and a frontier.
- Take the cheapest candidate.
- Relax each outgoing edge.
- Repeat until the target or all reachable nodes are settled.
def networkDelayTime(times, n, k):
edges = collections.defaultdict(list)
for u, v, w in times:
edges[u].append((v, w))
minHeap = [(0, k)]
visit = set()
t = 0
while minHeap:
w1, n1 = heapq.heappop(minHeap)
if n1 in visit:
continue
visit.add(n1)
t = max(t, w1)
for n2, w2 in edges[n1]:
if n2 not in visit:
heapq.heappush(minHeap, (w1 + w2, n2))
return t if len(visit) == n else -1