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

解析

一道典型的最短路径问题，可以使用 Dijkstra 算法解决。

dijkstra 算法是一种贪心算法，用于解决单源最短路径问题。它的基本思想是：从起点开始，每次选择一个距离起点最近的节点，然后以该节点为中心，更新与其相邻节点的距离。重复这个过程，直到所有节点都被遍历。

在近年来的研究中已经被证实，该算法已经是单源最短路径问题的全局最优解。

它基于一个原则，即已经被通过贪心算法确定的最短路径不会被修改。因此，每次选择距离起点最近的节点，就可以保证这个节点的最短路径是确定的。这个原则的前提是，图中的边权重不能为负数。

在这道题中，我们可以通过这样的解题思路。

首先，根据已知信息我们构建出加权邻接图。之后，我们通过 dijikstra 算法求出从节点 k 到所有节点的最短路径，然后取最大值确保所有节点都能接收到信号。如果存在不可达节点，则返回 -1。

另外，关于 dijkstra 算法的优化，关键点在于我们如何用最少的代价选择到剩余节点中距离起点最近的节点。我们可以使用最小堆来优化优先级队列，保证每次从队列中出队的已经是当前的最优解，从而减少重复运算。由于最小堆的实现比较复杂，这里就不展开了。

function networkDelayTime(times: number[][], n: number, k: number): number {
  // 构建加权邻接图
  const graph: IGraph = Array(n)
    .fill(null)
    .map(() => [] as IGraphNode[]);
  for (const [from, to, weight] of times) {
    graph[from - 1].push({ to: to - 1, weight: weight });
  }

  // 计算k到每个节点的加权距离
  const distances: Array<number> = dijkstra(graph, k - 1, n);
  // 从距离中取最大值，保证所有节点都收到信号
  const res = Math.max(...distances);
  // 若存在不可达节点，则返回 -1
  return res === Infinity ? -1 : res;
}

type IGraph = Array<Array<IGraphNode>>;
type IGraphNode = { to: number; weight: number };
type IPriorityQueue = Array<{ id: number; distToStart: number }>;

function dijkstra(graph: IGraph, start: number, vexNum: number): Array<number> {
  const distTo: number[] = new Array(vexNum).fill(Infinity);

  // 起点距离自己的最短距离是0
  distTo[start] = 0;

  // 这里可以通过最小堆优化，但是由于最小堆的实现比较复杂，这里使用数组模拟
  // const queue = new MinPriorityQueue();
  const queue: IPriorityQueue = [];
  queue.push({
    id: start,
    distToStart: 0
  });

  while (queue.length > 0) {
    const { id, distToStart } = queue.shift();
    // 如果当前节点距离起点已经大于最短路径了，剪枝
    if (distToStart > distTo[id]) {
      continue;
    }

    // 遍历所有邻接节点，以期望获取更小距离
    const neighbors = graph[id];
    for (const { to, weight } of neighbors) {
      // 判断从当前节点到相邻节点的这条加权路径是否更短
      const newDistance = distTo[id] + weight;
      if (newDistance < distTo[to]) {
        //  如果更短，更新相邻节点的最短路径
        // 由于该路径是可行的，将该路径信息加入到队列中等待下次递归
        distTo[to] = newDistance;
        queue.push({
          id: to,
          distToStart: newDistance
        });
        // console.log(`${start} -> ${to}: ${newDistance}`);
      }
    }
  }

  return distTo;
}