Leetcode 743. 网络延迟时间

末蓝、 2022-09-02 11:36 112阅读 0赞

#### 题目重述 ####

有 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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

弗洛伊德算法，找到最短路径，最后输出即可

这题使用弗洛伊德，是为了方便，考虑到本题是单源最短路径，且是有向图，可以采用深度优先遍历和缔结特斯拉算法来找到最短路径。

#### Java实现 ####

class Solution {
        
        private int maxTime = 0;
    
        public int networkDelayTime(int[][] times, int n, int k) {
        
    
            int[][] G = new int[n + 1][n + 1];
            for (int i = 1; i <=n ; i++) {
        
                for (int j = 1; j <=n ; j++) {
        
                    G[i][j] = 101;
                }
            }
            for (int[] item : times) {
        
                G[item[0]][item[1]] = item[2];
            }
            for (int z = 1; z <= n; z++) {
        
                for (int i = 1; i <= n; i++) {
        
                    for (int j = 1; j <= n; j++) {
        
                        if (G[i][j] > G[i][z] + G[z][j]) {
        
                            G[i][j] = G[i][z] + G[z][j];
                        }
                    }
                }
            }
            for (int i = 1; i <= n; i++) {
        
                if(i!=k)
                {
        
                    if(G[k][i] != 101)
                    {
        
                        maxTime = Math.max(maxTime,G[k][i]);
                    }else {
        
                        return -1;
                    }
                }
            }
            return maxTime;
        }