最短路径问题可以分为以下几类

  1. 对于无权图来说，使用BFS即可
  2. 对于有权图来说，可以使用迪杰斯特拉，直接使用BFS/DFS会超时，此时需要使用记忆化搜索（可以再升级为dp）
  3. 对于有边数限制或存在负权值的最短路径问题，不能使用dij，只能使用Bellman Ford和DFS/BFS记忆化搜索

743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：
c5fa613a9d9924415864054797873287_931_example_1.png
输入：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，没有什么套路

    1. class Solution {
    2.   int[][] graph;
    3.   int[] dist;
    4.   boolean[] vis;
    6.   public int networkDelayTime(int[][] times, int n, int k) {
    7.       graph = new int[n + 1][n + 1];    // 邻接矩阵
    8.       dist = new int[n + 1];    // 存储路径长度
    9.       vis = new boolean[n + 1];    // 表示节点是否被选取
    11.       //因为路径权值可能为0，因此需要初始化图为-1表示不可达
    12.       for (int[] neighbours : graph)
    13.           Arrays.fill(neighbours, -1);
    14.       //存图
    15.       for (int[] time : times) {
    16.           graph[time[0]][time[1]] = time[2];
    17.       }
    19.       dij(k, n);
    21.       //判断是否可以到达所有节点
    22.       for (int i = 1; i <= n; i++) {
    23.           if (!vis[i])
    24.               return -1;
    25.       }
    27.       //防止dist[0]干扰计算结果
    28.       dist[0] = Integer.MIN_VALUE;
    29.       return Arrays.stream(dist).max().getAsInt();
    30.   }
    32.   void dij(int k, int n) {
    33.       //起始先将所有节点标记为“未更新”和“距离无穷大”
    34.       Arrays.fill(dist, Integer.MAX_VALUE);
    35.       Arrays.fill(vis, false);
    36.       //起始节点距离为0
    37.       dist[k] = 0;
    39.       //dij每轮确定一个节点的最短路径，因此要循环n轮
    40.       for (int round = 0; round < n; round++) {
    41.           // target是本次挑选的目标节点
    42.           int target = -1;
    43.           // 挑选距离最短且未被更新的节点
    44.           for (int i = 1; i <= n; i++) {
    45.               if (!vis[i] && (target == -1 || dist[i] < dist[target]))
    46.                   target = i;
    47.           }
    49.           //如果没挑出来，说明剩余节点不可达，退出循环
    50.           if (dist[target] == Integer.MAX_VALUE)
    51.               break;
    52.           // 挑出一个节点target，更新vis数组
    53.           vis[target] = true;
    55.           //用刚挑出来的节点target来更新其他点的最小距离
    56.           for (int neighbour = 1; neighbour <= n; neighbour++) {
    57.               if (graph[target][neighbour] >= 0)
    58.                   dist[neighbour] = Math.min(dist[neighbour], dist[target] + graph[target][neighbour]);
    59.           }
    60.       }
    61.   }
    62. }

    787. K 站中转内最便宜的航班

    1129. 颜色交替的最短路径