88 lines
2.1 KiB
Markdown
88 lines
2.1 KiB
Markdown
|
---
|
||
|
|
layout: page
|
||
|
|
title: Network Delay Time
|
||
|
|
last_solved: 2020-06-19
|
||
|
|
category: graph, dijkstra
|
||
|
|
leetcode_url: https://leetcode.com/problems/network-delay-time
|
||
|
|
status: Attempted
|
||
|
|
---
|
||
|
|
|
||
|
|
Problem
|
||
|
|
-------
|
||
|
|
|
||
|
|
```
|
||
|
|
There are N network nodes, labelled 1 to N.
|
||
|
|
|
||
|
|
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
|
||
|
|
|
||
|
|
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
|
||
|
|
|
||
|
|
|
||
|
|
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
|
||
|
|
Output: 2
|
||
|
|
```
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
Solution
|
||
|
|
----------
|
||
|
|
|
||
|
|
Dijkstra is written very similar to BFS but with weights.
|
||
|
|
|
||
|
|
The end result of this problem is an array that keeps track of elaped time.
|
||
|
|
|
||
|
|
```
|
||
|
|
node 0,1,2,3,4 <-- index corresponds to node
|
||
|
|
elapsedTime: [0,1,0,1,2] <-- value corresponds to time for signal to reach node i from node K (ie: takes 2 seconds to reach node 4 from node 2)
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
{% highlight python %}
|
||
|
|
|
||
|
|
import heapq
|
||
|
|
from collections import deque
|
||
|
|
from collections import defaultdict
|
||
|
|
|
||
|
|
times = [[2,1,1],[2,3,1],[3,4,1]]
|
||
|
|
N = 4
|
||
|
|
K = 2
|
||
|
|
|
||
|
|
def networkDelayTime(times, N, K):
|
||
|
|
|
||
|
|
elapsedTime = [0] + [float("inf")] * N
|
||
|
|
graph = defaultdict(list)
|
||
|
|
heap = [(0, K)] # time, start node (ie: (0,2))
|
||
|
|
|
||
|
|
# add to adj hash table, where values = (edge,weight)
|
||
|
|
for u, v, w in times:
|
||
|
|
graph[u].append((v, w))
|
||
|
|
|
||
|
|
'''
|
||
|
|
graph:
|
||
|
|
2: [(1,1),(1,3)]
|
||
|
|
3: [(4,1)]
|
||
|
|
'''
|
||
|
|
|
||
|
|
while heap:
|
||
|
|
|
||
|
|
# pop off heap/queue
|
||
|
|
time, node = heapq.heappop(heap)
|
||
|
|
if time < elapsedTime[node]:
|
||
|
|
|
||
|
|
# process (add to elapsed time array)
|
||
|
|
elapsedTime[node] = time
|
||
|
|
|
||
|
|
# add neighbours, include weight
|
||
|
|
for v, w in graph[node]:
|
||
|
|
heapq.heappush(heap, (time + w, v)) # at node 3, add neighbour 4 (time+w, v)=(1+1,4) and heap=[(2,4)] -> time to reach node 4=2
|
||
|
|
|
||
|
|
|
||
|
|
mx = max(elapsedTime)
|
||
|
|
return mx if mx < float("inf") else -1
|
||
|
|
|
||
|
|
print( networkDelayTime(times, N, K) )
|
||
|
|
|
||
|
|
{% endhighlight %}
|
||
|
|
|
||
|
|
|