LeetCode - 743 网络延迟时间

题目来源

743. 网络延迟时间 - 力扣（LeetCode）

题目描述

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

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

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

示例

提示

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

题目解析

本题是典型的单源最短路径问题。

所谓“单源最短路径”，即图结构中，已某个点为源点，计算源点到另一个点之间的最短路径（即最小权重）。

要理解上面“单源最短路径”问题，我们需要有一些图结构的基础认识。

图结构由：顶点和边组成。比如下图中圆圈就是顶点，圆圈和圆圈之间的线就是边。

如果边是有方向的（即单向），则图称为有向图，

如果边是没有方向的（即双向），则图称为无向图。

边除了有方向性外，还有权重，所谓权重，可以简单理解为构成边的两个顶点之间的距离。如上图中顶点1和顶点2构成的边的权重就是1。

图中某个点想要到达另一个点可能存在多条路径，如下图从顶点2到达顶点7的路径有：

• 2 → 5 → 7 （权重11）
• 2 → 6 → 4 → 5 → 7（权重8）
• 2 → 6 → 4 → 3 → 7（权重7）
• 2 → 6 → 4 → 1 → 3 → 7（权重12）
• 2 → 6 → 1 → 3 → 7（权重13）

而其中路径权重最小的，即路径最短的只有一个，那就是2 → 6 → 4 → 3 → 7（权重7）

2 → 6 → 4 → 3 → 7就是要求的顶点2到顶点7的单源最短路径。

而本题是 “从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号”，即本题要求从K节点到剩余其他各店的单源最短路径，并返回这里最短路径中最大的那个。

在理解本题题意后，接下来我们考虑如何求解本题，而在求解本题前，我们必须要先将图结构通过代码模拟出来。

图结构的实现，有两种方式：

• 邻接矩阵
• 邻接表

比如上图用邻接矩阵模拟即为：

const x = Infinity;
const graph = [
    [0, x, x, x],
    [1, 0, 1, x],
    [x, x, 0, 1],
    [x, x, x, 0]
]

矩阵含义，若 graph[i][j] != Infinity，即表示 i+1顶点和j+1顶点相邻，且是i+1指向j+1，权重为graph[i][j]值。

上图如果用邻接表模拟即为：

const graph = {
    2: [[1,1], [3,1]]
    3: [[4,1]]
}

对象含义是graph对象的属性是起点，graph对象的属性值是一个数组，这是因为图中一个顶点可以和多个其他点相连，graph对象的属性值数组的元素还是数组，这是因为元素数组的第一个值是起点的邻接点，第二个值是起点到该邻接点的权重。

比如graph[2][1] = [3,1]，表示从顶点2出发，到邻接点3的权重是1。

对比来看，邻接表模拟图结构在内存消耗上代价更小，因此我们一般选择邻接表来模拟图结构。

接下来就是实现单源最短路径的求解算法了，这里其实可以使用图结构的两种遍历方法：

• 深度优先搜索，即dfs
• 广度优先搜索，即bfs

但是最短路径问题，一般不用dfs，因为深度优先搜索，需要将图结构中从源点出发的所有路径可能都找到，然后才能比较出最短路径，这种其实相当于暴力破解，性能非常低。

可能有人会有疑问，广度优先搜索不也相当于暴力吗？

的确，bfs和dfs其实都相当于暴力，但是bfs可以结合贪心算法思维，让最短路径的查找变为类似于二叉树的二分查找。

接下来我们通过图示来看看bfs结合贪心算法思维是如何实现图中单源最短路径的查找的：

下面我们需要求解下图中，从源点2到其他各点的最短路径

广度优先搜索，肯定是先搜索源点的直接临界点6和5。

我们假设源点2到自身的权重为0，则源点2到顶点6的权重为0+2，我们将其更小为顶点6的权重。

同理，我们将顶点5的权重更新为8。

这里顶点权重的含义是：从源点到达该顶点所需要花费的代价（即所经过边的权重累加之和）。

也就是说，从源点2触发，有两个选择，2→6和2→5，根据贪心算法思维，每个局部达到最优，则最终结果也会最优。

因此，我们选择权重更小的2→6。即我们认定从2出发，必然要选择6，可以理解为从2出发的第一条路径。

 接下来，我们将6当成出发点，则有两个选择，6→1和6→4 ，

此时顶点6的权重是2，而

• 6→1边权重为6，
• 6→4边权重为2，

因此从顶点6出发，到顶点4的代价更小，顶点4的权重为2+2。

接下来，从顶点4出发，有三个选择：

• 4 → 1 
• 4 → 3
• 4 → 5 

其中4 → 1 ，即 2 → 6 → 4 → 1 会让顶点1的权重变为7，这要比 2 → 6 → 1赋给顶点1的权重8要小，因此我们将顶点1的权重更新为7。

4 → 3，即 2 → 6 → 4 → 3会让顶点3的权重变为5。

4 → 5 ，即2 → 6 → 4 → 5会让顶点5的权重变为5，这要比 2 → 5赋给顶点5的权重8要小，因此我们将顶点5的权重更新为5.

因此，上面3条路径，我们有两个等价选择，即4 → 3或4 → 5 ，它们的总权重相同，因此我们都要试一下。

 我们可以先选择4 → 3

此时从顶点3出发，只有一条路径，即3→7，因此顶点7的权重设为5+2=7

接下来选择4→5

此时从顶点5出发，只有一条路径，即5→7，而此时顶点7的权重为5+3=8，大于之前3→7的赋予的权重7，因此不更新

此时，从源点2到到其他所有点的权重（最短路径）已经被全部求解出来了，

• 2 → 1（权重7）
• 2 → 3（权重5）
• 2 → 4（权重4）
• 2 → 5（权重5）
• 2 → 6（权重2）
• 2 → 7（权重7）

而以上，结合了广度优先搜索和贪心思维的算法就是Dijkstra算法，即迪杰斯特拉算法。

Dijkstra算法是专门用于求解图结构中单源最短路径问题，但是Dijkstra算法要求图结构中的边的权重值不能有负数。

Dijkstra算法的实现有一定的技巧，除了模拟图结构（使用邻接表）外，还需要定义一个长度为n（n为图结构中顶点的个数）的数组dist

dist数组的

• 索引值被当成对应顶点
• 元素值被当成源点到对应顶点的权重累计和

我们最终会将源点到各个顶点的最小权重值统计出来并保存在dist中，然后从dist中取出最大的即可最小权重即为题解。

dist数组初始时，会将源点到各个顶点的权重值设为Infinity，这样可以方便初次更新dist[i]顶点权重时必然成功，因为一般情况下顶点权重值都小于Infinity。

另外，我们实现Dijkstra算法，我们还需要一个优先队列，那么什么是优先队列，它的作用是什么呢？

优先队列(priority queue)：普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。

在Dijkstra算法中，优先队列用于存放每条路径的终点，优先级为终点的权重

比如上图中，初始时选择顶点2作为起点，此时从2出发有两条路径：

• 2 → 6
• 2 → 5

我们更新完顶点5，6的权重后，将顶点5，6加入优先队列。

根据贪心思维局部最优原则，下一步从优先队列中取出权重最小的顶点，作为新的起点，此时顶点6的权重更小，因此本质上我们是选择了2 → 6 路径的终点6再次出发，此时也有两条路径：

• 2 → 6  → 1
• 2 → 6  → 4

我们更新顶点1，4的权重后，将1，4加入优先队列。此时优先队列中记录的点如下：

• 5（本质是路径 2 → 5 的终点）
• 1（本质是路径 2 → 6  → 1 的终点）
• 4（本质是路径 2 → 6  → 4 的终点）

此时优先队列没有顶点6，因为顶点6已经被取出，如果不取出的话，则会产生问题，因为

2 → 6 的路径权重肯定要比 2 → 5、2 → 6  → 1、2 → 6  → 4都要小，如果不取出优先队列的顶点6，则后面优先队列中最小的总是6，产生死循环。

另外，我们需要思考一下，从最初的起点2出发，到达顶点6的最短路径，目前确认是 2 → 6,那么有没有一种可能，2 → 6 → x → ... → y → 6 的路径长度更短呢？

答案是不存在的，因为本题0 <= wi <= 100。

因此，本题只要是从优先队列出队的顶点，那么就可以确定该顶点已经找到了最小权重。

优先队列的作用就是用于缓存路径终点。并且根据贪心思维局部最优原则，终点的权重越小，则在优先队列中的优先级越高。

而一旦顶点被从优先队列中出队，则可以认为已经确定该顶点的权重为最小权重。

当优先队列中没有顶点时，表示所有顶点的到源点的最小权重已经找到。

JavaScript中没有优先队列数据结构，但是我们可以使用数组来模拟，当我们向数组中加入一个新顶点时，就执行数组排序，排序规则是权重小的顶点在队头，权重达的顶点在队尾。

---

2024.04.24

本题更新了一版更通用的解法。

之前的解法是有局限性的，或者说可能存在漏洞的。

漏洞是：优先队列存储的元素是节点编号。而元素的优先级排序，依赖于外部的dist数组。

// 优先队列，记录的是节点编号，节点距离源点的越近，则越优先出队
PriorityQueue pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
// 初始加入源点
pq.add(k);

我们需要知道优先队列只有在加入元素、以及取出元素时，会触发优先队列内部的元素优先级排序。

比如我们加入节点编号到优先队列，那么此时优先队列对内部元素i按照dist[i]进行重新排优先级。

但是，还有一种可能，那就是我们在节点编号 i 加入优先队列后，又再次改变了 dist[i] 的值，理论上此时我们应该将优先队列内部元素重新排序，但是实际上优先队列不支持该操作。

因此，为了避免这种情况，我们应该加入 【节点编号，节点到源点的距离】到优先队列中，即我们不能依赖于外部dist来判断优先级，而是要基于优先队列元素本身。

// 优先队列，记录的是【节点编号，源点到节点的距离】，节点距离源点的越近，则越优先出队
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// 初始加入源点
pq.add(【k, 0】);

举例如下：

单源最短路问题中，同一个节点重复加入优先队列是无法避免的，比如：

从源点2出发，此时节点6，5加入优先队列，pq = 【6, 5】

之后取出优先队列中最短路 2->6 的终点 6 继续bfs，此时节点1，4入队，pq = 【4，5，1】

之后取出优先队列中最短路 2->6->4 的终点 4 继续bfs，

此时发生了节点1，5重复入队的情况，pq = 【3, 1, 5, 5, 1】

由于每次遍历到点，都要尝试更新dist，比如源点2探索时，dist[5] 更新为8，节点4探索时，dist[5]更新为 5。

而优先队列只有在元素取出或加入时，才会（基于dist）内部调整各个元素的优先级排位，因此如果仅仅只改变dits，而不执行优先队列的取出、加入操作，那么此时优先队列内部优先级排位就是错的，后续我们再加入节点到优先队列时，是极大可能产生错误的优先级排位结果的。

节点重复入队无法避免，因此我们只能让相同节点差异化，即为每个入队节点附加一个实时的dist信息，比如源点2发起探索时，入队节点6，5，此时pq = 【[6, 2]，[5, 8]】，pq元素的含义是[节点编号, 此时节点到源点的距离]。

后续源点4发起探索时，再次入队节点5，实时dist为5，此时pq = 【[5, 8]，[5, 5]】

虽然重复入队了节点5，但是由于不同时段入队节点5的实时dist不同，所以不会产生问题。

Java算法源码

有局限性的解法

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 构建邻接表
        HashMapint[]>> graph = new HashMap<>();
        for (int[] time : times) {
            int u = time[0], v = time[1], w = time[2];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(new int[] {v, w});
        }
 
        // dist[i]表示节点i到源点的最短路
        int[] dist = new int[n + 1];
        // 初始时默认所有节点到源点都是无穷大距离
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 源点到自己距离为0
        dist[k] = 0;
 
        // 优先队列，记录的是节点编号，节点距离源点的越近，则越优先出队
        PriorityQueue pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
        // 初始加入源点
        pq.add(k);
 
        // bfs
        while (!pq.isEmpty()) {
            // pq中记录的都是各种路径的终点节点，我们取出这些路径中最短的那条的终点u
            int u = pq.poll();
 
            // 遍历节点u的下游节点
            if (graph.containsKey(u)) {
                for (int[] next : graph.get(u)) {
                    // 下游节点v, u到v的距离w
                    int v = next[0], w = next[1];
 
                    // 源点到u的距离是dist[u], u到v的距离w
                    // 则源点通过u到v的距离是 dist[u] + w
                    int newDist = dist[u] + w;
 
                    // 若此路更短，则更新源点到v的距离
                    if (dist[v] > newDist) {
                        dist[v] = newDist;
                        // 将新路终点v加入到优先队列参与下次比较
                        pq.add(v);
                    }
                }
            }
        }
 
        int ans = 0;
        for (int i = 1; i < dist.length; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

更通用的解法

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
 
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 构建邻接表
        HashMapint[]>> graph = new HashMap<>();
        for (int[] time : times) {
            int u = time[0], v = time[1], w = time[2];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(new int[]{v, w});
        }
 
        // visited[i] 表示是否找到了源点到节点i的最短路
        boolean[] visited = new boolean[n + 1];
 
        // dist[i]表示节点i到源点的最短路
        int[] dist = new int[n + 1];
        // 初始时默认所有节点到源点都是无穷大距离
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 源点到自己距离为0
        dist[k] = 0;
 
        // 优先队列，记录的是【节点编号, 源点到节点的距离】，源点到节点的距离越近，则越优先出队
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        // 初始加入源点
        pq.add(new int[]{k, 0});
 
        // bfs
        while (!pq.isEmpty()) {
            // pq中记录的都是各种路径的终点节点，我们取出这些路径中最短的那条的终点u
            int u = pq.poll()[0];
 
            // 如果visited[u]为true，表示之前已经找到了源点到u的最短路，则当前出队的u并非最短路的
            if (visited[u]) continue;
            // 否则记录找到了最短路u
            visited[u] = true;
 
            // 遍历节点u的下游节点
            if (graph.containsKey(u)) {
                for (int[] next : graph.get(u)) {
                    // 下游节点v, u到v的距离w
                    int v = next[0], w = next[1];
 
                    // 源点到u的距离是dist[u], u到v的距离w
                    // 则源点通过u到v的距离是 dist[u] + w
                    int newDist = dist[u] + w;
 
                    // 若此路更短，则更新源点到v的距离
                    if (dist[v] > newDist) {
                        dist[v] = newDist;
                        // 将新路终点v加入到优先队列参与下次比较
                        pq.add(new int[]{v, dist[v]});
                    }
                }
            }
        }
 
        int ans = 0;
        for (int i = 1; i < dist.length; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

JavaScript算法源码

有局限性的解法

var networkDelayTime = function (times, n, k) {
  // 邻接表
  const graph = {};
 
  // 初始化邻接表
  times.forEach((time) => {
    let [u, v, w] = time;
    graph[u] ? graph[u].push([v, w]) : (graph[u] = [[v, w]]);
  });
 
  // 源点k到其他点i的距离
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0; // 源点到自己的距离为0
 
  let needCheck = [k];
 
  while (needCheck.length > 0) {
    const k = needCheck.pop();
 
    if (graph[k]) {
      for (let [v, w] of graph[k]) {
        let newDist = dist[k] + w;
 
        if (dist[v] > newDist) {
          dist[v] = newDist;
          needCheck.push(v);
          needCheck.sort((a, b) => dist[b] - dist[a]);
        }
      }
    }
  }
 
  dist.shift();
  let ans = Math.max(...dist);
  return ans === Infinity ? -1 : ans;
};

更通用的解法

var networkDelayTime = function (times, n, k) {
  // 构建邻接表
  const graph = {};
  times.forEach((time) => {
    let [u, v, w] = time;
    graph[u] ? graph[u].push([v, w]) : (graph[u] = [[v, w]]);
  });
 
  // visited[i] 表示是否找到了源点到节点i的最短路
  const visited = new Array(n + 1).fill(false);
 
  // dist[i]表示节点i到源点的最短路, 初始时默认所有节点到源点都是无穷大距离
  const dist = new Array(n + 1).fill(Infinity);
  // 源点到自己的距离为0
  dist[k] = 0;
 
  // 优先队列，记录的是【节点编号, 源点到节点的距离】，源点到节点的距离越近，则越优先出队
  // 初始加入源点
  let pq = [[k, 0]];
 
  // bfs
  while (pq.length > 0) {
    // pq中记录的都是各种路径的终点节点，我们取出这些路径中最短的那条的终点u
    const u = pq.pop()[0];
 
    // 如果visited[u]为true，表示之前已经找到了源点到u的最短路，则当前出队的u并非最短路的
    if (visited[u]) continue;
    // 否则记录找到了最短路u
    visited[u] = true;
 
    // 遍历节点u的下游节点
    if (graph[u]) {
      // 下游节点v, u到v的距离w
      for (let [v, w] of graph[u]) {
        // 源点到u的距离是dist[u], u到v的距离w
        // 则源点通过u到v的距离是 dist[u] + w
        let newDist = dist[u] + w;
 
        // 若此路更短，则更新源点到v的距离
        if (dist[v] > newDist) {
          dist[v] = newDist;
          // 将新路终点v加入到优先队列参与下次比较
          pq.push([v, dist[v]]);
          // 按照“源点到节点的距离”降序，即pq尾巴是最短路径的终点
          pq.sort((a, b) => b[1] - a[1]);
        }
      }
    }
  }
 
  dist.shift();
  let ans = Math.max(...dist);
  return ans === Infinity ? -1 : ans;
};

Python算法源码

有局限性的解法

import heapq
import sys
 
 
class Solution(object):
    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        graph = {}
 
        for u, v, w in times:
            graph.setdefault(u, [])
            graph[u].append([v, w])
 
        dist = [sys.maxsize for _ in range(n + 1)]
        dist[k] = 0
 
        pq = []
        heapq.heappush(pq, (dist[k], k))
 
        while len(pq) > 0:
            _, k = heapq.heappop(pq)
 
            if graph.get(k):
                for v, w in graph[k]:
                    newDist = dist[k] + w
 
                    if dist[v] > newDist:
                        dist[v] = newDist
                        heapq.heappush(pq, (dist[v], v))
 
        ans = max(dist[1:])
 
        return -1 if ans == sys.maxsize else ans

更通用的解法

import heapq
import sys
 
 
class Solution(object):
    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        # 构建邻接表
        graph = {}
        for u, v, w in times:
            graph.setdefault(u, [])
            graph[u].append([v, w])
 
        # visited[i] 表示是否找到了源点到节点i的最短路
        visited = [False] * (n + 1)
 
        #  dist[i]表示节点i到源点的最短路, 初始时默认所有节点到源点都是无穷大距离
        dist = [sys.maxsize for _ in range(n + 1)]
        # 源点到自己距离为0
        dist[k] = 0
 
        #  优先队列，记录的是【源点到节点的距离, 节点编号】，源点到节点的距离越近，则越优先出队
        pq = []
        # 初始加入源点
        heapq.heappush(pq, (dist[k], k))
 
        # bfs
        while len(pq) > 0:
            # pq中记录的都是各种路径的终点节点，我们取出这些路径中最短的那条的终点u
            _, u = heapq.heappop(pq)
 
            # 如果visited[u]为true，表示之前已经找到了源点到u的最短路，则当前出队的u并非最短路的
            if visited[u]:
                continue
 
            # 否则记录找到了最短路u
            visited[u] = True
 
            # 遍历节点u的下游节点
            if graph.get(u):
                # 下游节点v, u到v的距离w
                for v, w in graph[u]:
                    # 源点到u的距离是dist[u], u到v的距离w
                    # 则源点通过u到v的距离是 dist[u] + w
                    newDist = dist[u] + w
 
                    # 若此路更短，则更新源点到v的距离
                    if dist[v] > newDist:
                        dist[v] = newDist
                        # 将新路终点v加入到优先队列参与下次比较
                        heapq.heappush(pq, (dist[v], v))
 
        ans = max(dist[1:])
 
        return -1 if ans == sys.maxsize else ans