题目

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->i
                if (!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;
    }
}