0743-网络延迟时间

题目描述

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

有 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) 对都互不相同（即，不含重复边）

思路：Floyd算法

将数据转化为邻接图（二维数组）存放，然后使用3重循环计算。

注意：

初始化的时候，要设置默认最大值，因为要做加法，所以不要使用 int.MaxValue ，可以使用其一半
遍历三重循环的时候，总是从头到尾，先遍历中间节点，再遍历起始和结束节点
输出结果的时候，去最大值，如果发现有极大值，说明reach不到，返回-1

csharp

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        // 测试 Floyd 算法
        // 1. 使用邻接图储存关系
        int[,] dp = new int[n+1,n+1];
        int INF = int.MaxValue / 2;

        // 2. 初始化为默认权重是极大值
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dp[i,j] = i == j ? 0 : INF;
            }
        }
        
        // 3. 填入数据
        for(int i=0; i<times.Length; i++){
            int source = times[i][0];
            int target = times[i][1];
            int weight = times[i][2];
            dp[source,target] = weight;
        }

        // 4. 状态转移
        // 遍历中间节点，起始节点，结束节点
        for(int i=1; i<=n; i++){
            for(int start=1; start<=n; start++){
                for(int end=1; end<=n; end++){
                    dp[start,end] = Math.Min(dp[start,end], dp[start,i] + dp[i,end]);
                }
            }
        }

        //遍历输出结果
        int ans = 0;
        //从节点k发出信号，找最大值
        for(int i=1; i<=n; i++){
            ans = Math.Max(ans,dp[k,i]);
        }

        return ans >= INF ? -1 : ans;
    }
}

思路: Dijkstra算法

主要差别在于， Floyd 是使用三重算法求出了所有的解， Dijkstra 使用单源，复杂度为 O(n^2)

Dijkstra 算法有两个辅助数组 visited 表示是否访问过该节点， dist 表示单源到达目的地的地址

csharp

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        // 测试 Floyd 算法
        // 1. 使用邻接图储存关系
        int[,] dp = new int[n+1,n+1];
        int INF = int.MaxValue / 2;

        // 2. 初始化为默认权重是极大值
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dp[i,j] = i == j ? 0 : INF;
            }
        }

        // 3. 填入数据
        for(int i=0; i<times.Length; i++){
            int source = times[i][0];
            int target = times[i][1];
            int weight = times[i][2];
            dp[source,target] = weight;
        }

        // 4. Dijkstra 算法
        bool[] visited = new bool[n+1]; //创建 visited 数组，记录中间节点是否已访问
        int[] dist = new int[n+1]; //创建 dist 数组，记录距离
        Array.Fill(dist,INF); //将默认距离设置为最大值
        dist[k]=0; //设置起始节点距离为0

        for(int p=1; p<=n; p++){ //迭代p次，为了能更新完所有路径
            int minLen = INF;
            int mid = 0; 
            //找到一个没有更新的最小的点，作为中间节点
            for(int i=1; i<=n; i++){
                if(!visited[i] && dist[i] < minLen){
                    mid = i;
                    minLen = dist[i];
                }
            }
            if(mid == 0){ //如果没有找到，直接退出
            	return;
            }

            for (int i = 1; i <= n; i++) {
                dist[i] = Math.Min(dist[i], dist[mid] + dp[mid,i]);
            }
            visited[mid] = true;
        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            ans = Math.Max(dist[i],ans);
        }

        return ans >= INF ? -1 : ans;
    }
}

0743-网络延迟时间 #

题目描述 #

思路：Floyd算法 #

思路: Dijkstra算法 #

0743-网络延迟时间

题目描述

思路：Floyd算法

思路: Dijkstra算法