題目
#

leetcode 743 - Network Delay Time (題目說明請點連結)

題目簡述
#

給定一個有向加權圖，從起始節點 k 發送信號，計算所有節點收到信號所需的最短時間。如果無法到達所有節點，則返回 -1。

範例
#

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: 從節點 2 開始，所有節點都能在 2 個時間單位內收到信號。

graph TD; A[2] B[1] C[3] D[4] A -->|1| B A -->|1| C C -->|1| D

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation: 從節點 1 開始，節點 2 在 1 個時間單位內收到信號。

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: 從節點 2 開始，無法到達節點 1。

解題思路
#

這題的目標是計算從起始節點 k 發送信號，所有節點收到信號所需的最短時間。若有任何節點無法被到達，則回傳 -1。換句話說，就是要找出從 k 出發到所有其他節點的最短路徑中，所需時間的最大值。

解法
#

Dijkstra

每次選擇當前距離最小的節點進行處理
一旦確定某個節點的最短距離，它就是最終的最短距離
確保每次處理的都是當前距離最小的節點，提高效率

步驟
#

建圖
- 使用鄰接表表示圖
- 每個節點存儲其鄰居節點和邊權重
初始化
- 使用優先佇列（最小堆）來選擇當前距離最小的節點
- 從起始節點開始，距離設為 0
執行 Dijkstra
- 每次從優先佇列中取出距離最小的節點
- 更新該節點所有鄰居的距離
- 重複直到所有節點都被處理
計算結果
- 檢查是否所有節點都能到達
- 返回所有最短路徑中的最大值

例子說明
#

輸入： times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

graph TD; A[2] B[1] C[3] D[4] A -->|1| B A -->|1| C C -->|1| D

步驟 1：建立圖結構

節點 2 → 節點 1 (時間 1)
節點 2 → 節點 3 (時間 1)  
節點 3 → 節點 4 (時間 1)

步驟 2：執行 Dijkstra 演算法

處理順序	當前節點	距離	更新鄰居	優先佇列狀態
1	節點 2	0	節點 1(1), 節點 3(1)	[(1,1), (3,1)]
2	節點 1	1	無鄰居	[(3,1)]
3	節點 3	1	節點 4(2)	[(4,2)]
4	節點 4	2	無鄰居	[]

步驟 3：最終結果

節點 1：距離 1
節點 2：距離 0（起始節點）
節點 3：距離 1
節點 4：距離 2

答案： 2（所有節點收到信號時間的最大值）

完整程式碼
#

java

import java.util.*;

class Solution {
   public int networkDelayTime(int[][] times, int n, int k) {
        // 1. 建立鄰接表 graph - 用於存儲圖的結構
        Map<Integer, List<int[]>> graph = new HashMap<>();
        // 初始化所有節點的鄰接表，每個節點對應一個空的鄰居列表
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        // 將邊的信息加入鄰接表，times[i] = [起始節點, 目標節點, 權重]
        for (int[] time : times) {
            int u = time[0], v = time[1], w = time[2]; // u: 起始節點, v: 目標節點, w: 邊權重
            graph.get(u).add(new int[]{v, w}); // 將目標節點和權重加入起始節點的鄰居列表
        }

        // 2. 使用 Dijkstra 演算法 (Min Heap) - 優先佇列確保每次處理距離最小的節點
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); // 按距離排序的最小堆
        pq.offer(new int[]{k, 0}); // 將起始節點加入佇列，距離為0
        Map<Integer, Integer> dist = new HashMap<>(); // 存儲每個節點的最短距離
        
        // 執行 Dijkstra 演算法主迴圈
        while (!pq.isEmpty()) {
            int[] curr = pq.poll(); // 取出距離最小的節點
            int node = curr[0], time = curr[1]; // node: 當前節點, time: 到當前節點的距離

            if (dist.containsKey(node)) continue; // 如果已經找到該節點的最短距離，跳過（避免重複處理）
            dist.put(node, time); // 記錄當前節點的最短距離

            // 遍歷當前節點的所有鄰居，更新它們的距離
            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0], weight = neighbor[1]; // nextNode: 鄰居節點, weight: 邊權重
                if (!dist.containsKey(nextNode)) { // 如果鄰居節點還沒有找到最短距離
                    pq.offer(new int[]{nextNode, time + weight}); // 將鄰居節點加入佇列，距離為當前距離+邊權重
                }
            }
        }

        // 3. 檢查是否所有節點都能到達並返回結果
        if (dist.size() < n) return -1; // 如果有節點無法到達，返回-1
        return Collections.max(dist.values()); // 返回所有節點中最短距離的最大值，即所有節點收到信號的時間
    }

}