LeetCode 筆記 - 743. Network Delay Time

題目在此 743. Network Delay Time

看到這題的時候,感覺好像在考閱讀測驗
給定一個 Graph 與每個邊的方向與權重,指定一個 node 計算出訊號抵達所有 node 的時間

解題思維

這題就是要你各位實作 Dijkstra’s algorithm
完成✅image 106

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:

# times[i] = (ui, vi, wi)
# ui: source node
# vi: target node
# wi: time to reach from ui to vi
# n: number of nodes
# k: starting node

def dijkstra(start):

# priority_queue is a priority queue that stores (the shortest dis from start node, node)
priority_queue = []
heapq.heappush(priority_queue, (0, start_node))

# dist is a dict that stores (node, the shortest dis from the current node)
dis_table = collections.defaultdict(lambda: 20000)
dis_table[start_node] = 0

while priority_queue:
# shortest_dis: the dis from start node
# current_node: current node

# pop the node with the smallest dis from start node
shortest_dis, current_node = heapq.heappop(priority_queue)
if dist[current_node] < shortest_dis:
# if the dis from start node is smaller than the dis from start node
# of the current node, then skip
continue

# for each neighbor of the current node
for adjacent_node, dis in graph[current_node]:
cost = shortest_dis + dis
if cost < dist[adjacent_node]:
dist[adjacent_node] = cost
heapq.heappush(priority_queue, (cost, adjacent_node))

return dist

graph = collections.defaultdict(list)
for u_node, v_node, dis in times:
graph[u_node].append((v_node, dis))

result = dijkstra(k)
return max(result.values()) if len(result) == n else -1
image 106

相關文章