Network Delay Time
- 1 min read
- Graph
- LC-Medium
3 years ago
Solution
- Use Dijkstra's Shortest Path Algorithm
- Kinda similar to Min Cost to Connect All Points wherein you use a min heap
- Start from given node
k, mark as visited, add all neighbours to minheap, keeping in mind that the distance to get to this neighbour node is not just the distance from current node to the neighbour, but distance travelled overall - Whenever we've visited all nodes, immediately return
- If return statement is not reached, it means all nodes weren't reachable, so return -1
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj = defaultdict(list)
for u, v, w in times:
adj[u].append((w, v))
# No need of updating weights if newer distance found since the aim is not to find the global shortest path but immediate shortest path
vis = set()
q = [(0, k)]
while q:
time, node = heappop(q)
vis.add(node)
if len(vis) == n:
return time
for nbr_time, nbr in adj[node]:
if nbr not in vis:
heappush(q, (time + nbr_time, nbr))
return -1