## [743\. 網絡延遲時間](https://leetcode-cn.com/problems/network-delay-time/) > Medium #### 思路 `雙周賽 #27` 和 `周賽 #193` 碰到了兩道圖的題目，[課程安排 IV](../contest/course-schedule-iv.md) 學習了，Floyd算法（多源最短路徑算法）。同時接觸到了Dijkstra 同源最短路徑算法，但是一直沒有時間學習。通過這道題，邊學習邊嘗試寫一下。 **Dijkstra算法學習** >有關Dijkstra的解釋，看完以下的文章就理解了，講的非常清晰 > * [https://www.codingame.com/playgrounds/1608/shortest-paths-with-dijkstras-algorithm/introduction](https://www.codingame.com/playgrounds/1608/shortest-paths-with-dijkstras-algorithm/introduction) > * [https://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html](https://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html) >圖的問題，無論是使用什么算法，基本上我們都需要構造鄰接圖或鄰接矩陣。看完下面的文章，應該可以掌握了 >* [https://www.jianshu.com/p/ce4109962031](https://www.jianshu.com/p/ce4109962031) >* [https://www.jianshu.com/p/fbbabb0331ce](https://www.jianshu.com/p/fbbabb0331ce) **新手總結** * **鄰接表的構造**，我們可以使用矩陣的方式，即**鄰接矩陣**。矩陣有兩個維度，可以表示方向。矩陣的值用于存放帶權圖中的權重，比如，所花時間，費用，距離等等 * **dis數組**，還需要使用一個一維數組，用于存放點到目標點的距離。根據鄰接矩陣初始化，經過對當前點的關聯點的遍歷和距離計算，更新數組中到當前點的距離值。 * **dis數組的更新**，下一個點選用`dis數組`中距離當前點最近的點開始，不斷更新距離值，這個操作叫做`松弛` * **path數組**， 本題沒有用到，但是假如我們就要找到最短路徑并且打印出該路徑。我們就需要使用一個數組用于存放所走的路徑。每次更新`dis數組`時，說明我們找到一條更近的路徑，我們就需要將這個節點更新到`path數組`當中。具體可以查閱Disjkstra算法學習的第一個鏈接。 **回到本題** * 再回到這道題，其實已經很明顯了。題目給定了一個帶權有向圖，并且指定從某個點出發，正好符合Dijkstra算法的使用場景。 * 重新理解提議，題目就是求到達所有點的最小路徑的中取最大值。 * 首先構造有向圖的鄰接表。 * 從k點出發，如果遍歷鄰接表結束后，最終還有節點沒有訪問到。說明無法使所有節點都達到，返回`-1` 以上，知識儲備已就位，嘗試寫一下代碼，AC！ #### 代碼 python3 ``` class Solution: # 根據當前節點，選出距離當前節點最近的節點 def closestNode(self, visited, node, dis): temp = math.inf cur_node = 0 for n in range(len(dis)): if n not in visited and n != 0 and n != node: if dis[n] < temp: temp = dis[n] cur_node = n return cur_node def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int: # 構造鄰接表/鄰接矩陣 graph = [[math.inf for _ in range(N+1)] for _ in range(N+1)] # 多個(0,0),這樣使符合題目中節點值等于下標 for t in times: graph[t[0]][t[1]] = t[2] for n in range(N+1): graph[n][n] = 0 visited = set() dis = [math.inf] * (N + 1) # 記錄節點的距離，index代表數字，多個0 for n in range(N+1): dis[n] = graph[K][n] dis[0] = -1 dis[K] = 0 cur_node = K for _ in range(N+1): for d in range(1, len(dis)): if (dis[cur_node] + graph[cur_node][d]) < dis[d]: dis[d] = dis[cur_node] + graph[cur_node][d] visited.add(cur_node) cur_node = self.closestNode(visited, cur_node, dis) result = max(dis) return result if result < math.inf else -1 ```