743. 网络延迟时间(中等)

1，问题描述

743. 网络延迟时间

难度：中等

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

2，初步思考

​ 看题大概就是更新k节点其他所有其他节点的最短路径，然后输出最大值

​ 那么就直接使用dijistra最短路径算法来处理

3，代码处理

import java.util.Arrays;
import java.util.PriorityQueue;

public class _743网络延迟时间 {

    // dijistra算法求解：使用优先队列来进行处理
    public int networkDelayTime_pq(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE / 2;// 邻接矩阵初始化最大值
        int[][] graph = new int[n][n];// 邻接矩阵
        int[] distance = new int[n];// 记录最短距离
        boolean[] visited = new boolean[n];// 记录是否访问过
        int[] parent = new int[n];// 前驱顶点

        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
        }
        for (int[] time : times) {
            graph[time[0] - 1][time[1] - 1] = time[2];
        }// 构建邻接矩阵

        for (int i = 0; i < n; i++) {
            distance[i] = INF;
            visited[i] = false;
            parent[i] = -1;
            graph[i][i] = 0;
        }
        distance[k - 1] = 0;
        parent[k - 1] = k - 1;

        // 使用优先队列进行处理
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        pq.offer(new int[]{0, k - 1});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int time = cur[0];
            int curNode = cur[1];
            if (time > distance[curNode]) {// 直接过滤重复添加的数据
                continue;
            }
            for (int i = 0; i < n; i++) {
                if (i == curNode) continue;
                int d = distance[curNode] + graph[curNode][i];
                if (d < distance[i]) {
                    distance[i] = d;
                    pq.offer(new int[]{d, i});
                }
            }
        }
        int ans = Arrays.stream(distance).max().getAsInt();
        return ans == INF ? -1 : ans;
    }


    // dijistra算法求解：自己编写的
    public int networkDelayTime(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE / 2;// 邻接矩阵初始化最大值
        int[][] graph = new int[n][n];// 邻接矩阵
        int[] distance = new int[n];// 记录最短距离
        boolean[] visited = new boolean[n];// 记录是否访问过
        int[] parent = new int[n];// 前驱顶点

        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
        }
        for (int[] time : times) {
            graph[time[0] - 1][time[1] - 1] = time[2];
        }// 构建邻接矩阵

        for (int i = 0; i < n; i++) {
            distance[i] = INF;
            visited[i] = false;
            parent[i] = -1;
            graph[i][i] = 0;
        }
        distance[k - 1] = 0;
        parent[k - 1] = k - 1;
        visited[k - 1] = true;
        for (int i = 0; i < n; i++) {
            distance[i] = graph[k - 1][i];
        }

        // 2. 开始遍历
        for (int i = 0; i < n - 1; i++) {// 只用遍历n-1次，因为起始节点已经被访问过
            int nextIdx = -1;
            int minDistance = INF;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && distance[j] < minDistance) {
                    nextIdx = j;
                    minDistance = distance[j];
                }
            }// 目的：找到距离最小的顶点（需要过滤已被访问过的顶点）

            if (nextIdx == -1) return -1;// 没有顶点可以访问，说明不可达
            visited[nextIdx] = true;// 直接标记为访问过
            for (int j = 0; j < n; j++) {
                if (!visited[j] && minDistance + graph[nextIdx][j] < distance[j]) {
                    distance[j] = minDistance + graph[nextIdx][j];
                    parent[j] = nextIdx;
                }
            }
        }

        int asInt = Arrays.stream(distance).max().getAsInt();
        return asInt == INF ? -1 : asInt;
    }

    // 官方题解1
    public int networkDelayTime_gov1(int[][] times, int n, int k) {
        final int INF = Integer.MAX_VALUE / 2;
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], INF);
        }
        for (int[] t : times) {
            int x = t[0] - 1, y = t[1] - 1;
            g[x][y] = t[2];
        }// 整理有向图

        int[] dist = new int[n];// 记录最短距离
        Arrays.fill(dist, INF);// 填充最大值
        dist[k - 1] = 0;// 源点到源点的最短距离为0
        boolean[] used = new boolean[n];// 记录是否访问过

        for (int i = 0; i < n; ++i) {
            int x = -1;
            for (int y = 0; y < n; ++y) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            used[x] = true;
            for (int y = 0; y < n; ++y) {
                dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
            }
        }

        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;
    }

    public static void main(String[] args) {
        _743网络延迟时间 networkDelayTime = new _743网络延迟时间();
        System.out.println(networkDelayTime.networkDelayTime_pq(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
    }
}