題目

https://leetcode.com/problems/network-delay-time/

題解

有向圖，求源點到所有頂點的最短距離，經典 Dijkstra 算法，只要知道思路就能實現，然而每次思路都要重新查一遍，過幾個月又忘了。。

Dijkstra 算法

1）Dijkstra 算法必須指定一個源點
2）生成一個源點到各個點的最小距離表，一開始只有一條記錄，即原點到自己的最小距離為0，源點到其他所有點的最小距離都為正無窮大
3）從距離表中拿出沒拿過記錄里的最小記錄，通過這個點發出的邊，更新源點到各個點的最小距離表，不斷重復這一步
4）源點到所有的點記錄如果都被拿過一遍，過程停止，最小距離表得到了

草稿

實現的時候，我一開始有個更新細節寫錯了（line 29），照著三葉的 答案 對比了一下，改過來了，才 AC。

另外，Dijkstra 是可以用 heap 做優化的，詳見答案，有空再優化下。

class Solution {public int networkDelayTime(int[][] times, int n, int k) {int[][] edge = new int[n + 1][n + 1];for (int i = 0; i <= n; i++) {Arrays.fill(edge[i], Integer.MAX_VALUE);edge[i][i] = 0;}for (int[] t : times) {edge[t[0]][t[1]] = t[2];}int[] dist = new int[n + 1];boolean[] visited = new boolean[n + 1];for (int i = 0; i <= n; i++) {dist[i] = edge[k][i];}visited[k] = true;int count = 1;while (count < n) {int idx = 0;for (int i = 1; i <= n; i++) {if (!visited[i] && dist[idx] > dist[i]) idx = i;}visited[idx] = true;count++;for (int i = 1; i <= n; i++) { // k->idx->iif (!visited[i] && edge[idx][i] != Integer.MAX_VALUE && dist[idx] + edge[idx][i] < dist[i]) {dist[i] = dist[idx] + edge[idx][i]; // k->i = k->idx(=dist[idx]) + idx->i}}}int result = 0;for (int i = 1; i <= n; i++) {result = Math.max(result, dist[i]);}return result == Integer.MAX_VALUE ? -1 : result;} }

總結

以上是生活随笔為你收集整理的leetcode 743. Network Delay Time | 743. 网络延迟时间（邻接矩阵，Dijkstra 算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。