LeetCode_dijkstra算法_中等_743. 网络延迟时间

男娘i 2023-10-06 22:37 21阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过有向边的传递时间。 times\[i\] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

**示例 1：**  
![在这里插入图片描述][3439fbfec440465183eb188aa4937ddb.png]  
输入：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 算法变成了默写题][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;
            }
        }
    }

[3439fbfec440465183eb188aa4937ddb.png]: https://img-blog.csdnimg.cn/3439fbfec440465183eb188aa4937ddb.png
[DIJKSTRA]: https://labuladong.github.io/algo/2/20/55/