1.题目

有 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

示例 2：
输入：times = 1,2,1, n = 2, k = 1
输出：1

示例 3：
输入：times = 1,2,1, n = 2, k = 2
输出：-1

提示：
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都互不相同（即，不含重复边）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/network-delay-time

2.思路

（1）dijkstra算法
思路参考我写了一个模板，把 DIJKSTRA 算法变成了默写题。

3.代码实现（Java）

//思路1————dijkstra算法
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        //节点编号从 1 开始，使用邻接表来存储图
        List<int[]>[] graph = new LinkedList[n + 1];
        //创建 n 个节点
        for (int i = 1; i <= n; i++) {
            graph[i] = new LinkedList<>();
        }
        //根据数组 times 中的信息创建节点之间的边
        for (int[] edge : times) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            //from -> List<(to, weight)>
            graph[from].add(new int[]{to, weight});
        }
        int[] dist = dijkstra(k, graph);
        //由于要使所有节点都收到信号，故需找到最长的那一条最短路径
        int res = 0;
        for (int i = 1; i < dist.length; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                //有节点不可达，故直接返回 -1
                return -1;
            } else {
                res = Math.max(res, dist[i]);
            }
        }
        return res;
    }

    //输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
    public int[] dijkstra(int start, List<int[]>[] graph){
        //dist[i] = dis: 起点 start 到节点 i 的最短路径长度
        int[] dist = new int[graph.length];
        //初始化 dist，dist[i] = Integer.MAX_VALUE表明起点到节点 i 之间不可达
        Arrays.fill(dist, Integer.MAX_VALUE);
        //起点与自己之间的最短路径长度为 0
        dist[start] = 0;
        //定义优先级队列，distFromStart值较小的元素排在队首
        Queue<State> queue = new PriorityQueue<>((a, b) -> {
            //返回值为正数则交换 a 和 b
            return a.distFromStart - b.distFromStart;
        });
        //从起点 start 开始进行 BFS
        queue.offer(new State(start, 0));
        while (!queue.isEmpty()) {
            //取出队首元素
            State curState = queue.poll();
            int curNodeID = curState.id;
            int curDistFromStart = curState.distFromStart;
            if (curDistFromStart > dist[curNodeID]) {
                continue;
            }
            //将与当前节点相邻的所有节点存入队列
            for (int[] neighbor : graph[curNodeID]) {
                int nextNodeID = neighbor[0];
                int distToNextNode = dist[curNodeID] + neighbor[1];
                //更新 dist
                if (dist[nextNodeID] > distToNextNode) {
                    dist[nextNodeID] = distToNextNode;
                    queue.offer(new State(nextNodeID, distToNextNode));
                }
            }
        }
        return dist;
    }

    class State {
        // 图节点的 id
        int id;
        // 从 start 节点到当前节点的距离
        int distFromStart;

        public State(int id, int distFromStart) {
            this.id = id;
            this.distFromStart = distFromStart;
        }
    }
}