LeetCode 筆記 - 2642. Design Graph With Shortest Path Calculator

Posted on

題目在此 2642. Design Graph With Shortest Path Calculator

給定一個 Graph 與每個邊的方向與權重，指定一個 node 計算出訊號抵達所有 node 的時間。

解題思維

名詞解說：

這題就是要你實作 Dijkstra’s algorithm，難點是在於需要實作完之後，再加上一些快取方式來應對連續的存取。
如果你還沒有實作過 Dijkstra’s algorithm，可以先解解看 743. Network Delay Time 這題，這題是簡單經典版。image 106

可以自己多做幾次，熟悉一下 Dijkstra’s algorithm 的實作方式，因為這個演算法在面試中出現的機率很高。

程式碼

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
class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.graph = [set() for _ in range(n)]

        for from_node, to_node, cost in edges:
            self.graph[from_node].add((cost, to_node))

        self.n = n

    def addEdge(self, edge: List[int]) -> None:
        from_node, to_node, cost = edge

        self.graph[from_node].add((cost, to_node))

    def shortestPath(self, node1: int, node2: int) -> int:
        dis_table = [int(1e9) for _ in range(self.n)]
        dis_table[node1] = 0

        priority_queue = []
        heapq.heappush(priority_queue, (0, node1))

        while priority_queue:
            current_cost, current_node = heapq.heappop(priority_queue)

            # 如果 node2 已經是最短路徑了，就可以直接回傳
            if current_node == node2:
                return current_cost

            if dis_table[current_node] < current_cost:
                continue

            for cost, adjust_node in self.graph[current_node]:
                new_cost = current_cost + cost

                if new_cost < dis_table[adjust_node]:
                    dis_table[adjust_node] = new_cost
                    heapq.heappush(priority_queue, (new_cost, adjust_node))

        return -1
image 106

相關文章