有?n?個網絡節點，標記為?1?到?n。

給你一個列表?times，表示信號經過?有向?邊的傳遞時間。?times[i] = (ui, vi, wi)，其中?ui?是源節點，vi?是目標節點，?wi?是一個信號從源節點傳遞到目標節點的時間。

現在，從某個節點?K?發出一個信號。需要多久才能使所有節點都收到信號？如果不能使所有節點收到信號，返回?-1?。

示例 1：

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

算法流程

1. 初始化：

   • 鄰接矩陣?g?存儲邊權。

   • dis?數組存儲源點到各點的最短距離，初始為?INF。

   • done?數組標記節點是否已確定最短路徑。

2. Dijkstra 主循環：

   • 選擇當前未處理的、距離最短的節點?x。

   • 如果?x?不可達，返回?-1。

   • 更新?maxDis?為?dis[x]（因為?dis[x]?是遞增的）。

   • 標記?x?為已處理。

   • 松弛?x?的所有鄰居?y，更新?dis[y]。

3. 終止條件：

   • 所有節點已處理，返回?maxDis（最長延遲時間）。

時間復雜度

• 鄰接矩陣實現：O(n^2)（適用于稠密圖）。

• 堆優化（優先隊列）：O(E log V)（適用于稀疏圖，但本題未使用）。

空間復雜度

• O(n^2)（鄰接矩陣存儲）。

1. 初始化

final int INF = Integer.MAX_VALUE / 2; // 防止加法溢出
int[][] g = new int[n][n]; // 鄰接矩陣
for (int[] row : g) {Arrays.fill(row, INF);
}

• INF：表示“無窮大”，用于初始化不可達的邊。Integer.MAX_VALUE / 2?是為了防止后續計算?dis[x] + g[x][y]?時溢出。

• g：鄰接矩陣，g[i][j]?表示從節點?i?到?j?的傳輸時間（權重）。

• 初始化鄰接矩陣：所有邊初始為?INF（表示初始時所有節點之間不可達）。

---

2. 構建圖的鄰接矩陣

for (int[] t : times) {g[t[0] - 1][t[1] - 1] = t[2];
}

• times?是一個二維數組，其中?times[i] = [u, v, w]?表示從節點?u?到?v?的傳輸時間為?w。

• 存儲到鄰接矩陣：

  • g[t[0] - 1][t[1] - 1] = t[2]：因為節點編號從?1?開始，而數組索引從?0?開始，所以需要?-1?調整。

---

3. Dijkstra 算法初始化

int maxDis = 0;
int[] dis = new int[n];
Arrays.fill(dis, INF);
dis[k - 1] = 0;
boolean[] done = new boolean[n];

• maxDis：記錄所有最短路徑中的最大值（即網絡延遲時間）。

• dis：dis[i]?表示從源節點?k?到節點?i?的最短距離，初始為?INF（不可達）。

• dis[k - 1] = 0：源節點到自身的距離為?0。

• done：標記節點是否已經確定最短路徑。

---

4. Dijkstra 主循環

while (true) {int x = -1;for (int i = 0; i < n; i++) {if (!done[i] && (x < 0 || dis[i] < dis[x])) {x = i;}}if (x < 0) {return maxDis; // 所有節點已處理完畢}if (dis[x] == INF) { // 有節點無法到達return -1;}maxDis = dis[x]; // 更新最大延遲時間done[x] = true; // 標記 x 的最短路徑已確定for (int y = 0; y < n; y++) {dis[y] = Math.min(dis[y], dis[x] + g[x][y]);}
}

(1) 選擇當前未處理的最短路徑節點

int x = -1;
for (int i = 0; i < n; i++) {if (!done[i] && (x < 0 || dis[i] < dis[x])) {x = i;}
}

• x：當前未處理（!done[i]）且距離?dis[i]?最小的節點。

• 貪心策略：每次選擇距離源節點最近的未處理節點進行擴展。

(2) 檢查是否所有節點已處理

if (x < 0) {return maxDis; // 所有節點已處理完畢
}

• x < 0：表示所有節點都已處理，返回?maxDis（即最長延遲時間）。

(3) 檢查是否有節點不可達

if (dis[x] == INF) { // 有節點無法到達return -1;
}

• dis[x] == INF：表示當前節點?x?無法從源節點到達，直接返回?-1。

(4) 更新?maxDis?并標記?x?為已處理

maxDis = dis[x]; // 更新最大延遲時間
done[x] = true; // 標記 x 的最短路徑已確定

• maxDis：由于 Dijkstra 每次處理的?dis[x]?是遞增的，所以直接更新即可。

• done[x] = true：表示?x?的最短路徑已確定，后續不再更新。

(5) 松弛操作（更新鄰居的最短距離）

for (int y = 0; y < n; y++) {dis[y] = Math.min(dis[y], dis[x] + g[x][y]);
}

• 松弛（Relaxation）：嘗試通過?x?縮短?y?的最短路徑：

  • 如果?dis[x] + g[x][y] < dis[y]，則更新?dis[y]。

完整版代碼：

class Solution {public int networkDelayTime(int[][] times, int n, int k) {final int INF = Integer.MAX_VALUE / 2; // 防止加法溢出int[][] g = new int[n][n]; // 鄰接矩陣for (int[] row : g) {Arrays.fill(row, INF);}for (int[] t : times) {g[t[0] - 1][t[1] - 1] = t[2];}int maxDis = 0;int[] dis = new int[n];Arrays.fill(dis, INF);dis[k - 1] = 0;boolean[] done = new boolean[n];while (true) {int x = -1;for (int i = 0; i < n; i++) {if (!done[i] && (x < 0 || dis[i] < dis[x])) {x = i;}}if (x < 0) {return maxDis; // 最后一次算出的最短路就是最大的}if (dis[x] == INF) { // 有節點無法到達return -1;}maxDis = dis[x]; // 求出的最短路會越來越大done[x] = true; // 最短路長度已確定（無法變得更小）for (int y = 0; y < n; y++) {// 更新 x 的鄰居的最短路dis[y] = Math.min(dis[y], dis[x] + g[x][y]);}}}
}

?

示例

輸入：

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

執行流程：

1. 初始化：

   • dis = [INF, 0, INF, INF]（源節點?k=2?的距離為?0）。

2. 第一次循環：

   • 選擇?x=1（dis[1] = 0）。

   • 松弛鄰居?y=0?和?y=2：

     • dis[0] = min(INF, 0 + 1) = 1

     • dis[2] = min(INF, 0 + 1) = 1

   • maxDis = 0。

3. 第二次循環：

   • 選擇?x=0?或?x=2（dis[0] = 1,?dis[2] = 1）。

   • 假設選?x=0，但沒有鄰居可更新。

   • maxDis = 1。

4. 第三次循環：

   • 選擇?x=2。

   • 松弛鄰居?y=3：

     • dis[3] = min(INF, 1 + 1) = 2

   • maxDis = 1。

5. 第四次循環：

   • 選擇?x=3。

   • 沒有鄰居可更新。

   • maxDis = 2。

6. 結束：

   • 所有節點已處理，返回?maxDis = 2。

最終輸出：2（最長延遲時間）。