各类最短路模板 | Foufor Past = FP 的一亩三分地

参考：涵盖所有「存图方式」与「最短路算法」(史上最全)

1. 存图方式

1.1 邻接矩阵（稠密图）

使用二维矩阵来存图。

// w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] g = new int[N][N];

// 加边操作
void add(int a, int b, int c) {
    g[a][b] = c;
}

1.2 邻接表（稀疏图）

即链式前向星。

int[] head = new int[N], e = new int[M], next = new int[M], w = new int[M];

// 加边操作
void add(int a, int b, int c) {
    e[idx] = b;
    next[idx] = head[a];
    w[idx] = c;
    head[a] = idx++;
}

// 遍历以某个节点为起点的边
for (int i = head[a]; i != -1; i = next[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c
}

1.3 二维列表

List<Integer>[] g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (int[] e : edges) {
    int x = e[0], y = e[1];
    g[x].add(y);
    g[y].add(x);
}
// 遍历
for (int y : g[x]) {
    if (y != fa) {
        
    }
}

2. 最短路算法

2.1 Floyd算法（Floyd-Warshall算法），适合有向图或无向图、负权边、多源最短路，可以判定负权环

参考带你发明 Floyd 算法：从记忆化搜索到递推

2959. 关闭分部的可行集合数目 - 力扣（LeetCode）这道题可以加深对Floyd算法本质的理解。

适用范围：

Floyd-Warshall算法适用于解决图中所有节点对之间最短路径的问题，包括有向图或无向图，可以处理带有负权边和负权环的情况。

适用于有向图或无向图。
适用于边权重可能为负值的情况。
适用于检测图中是否存在负权环。

算法流程：

初始化： 创建一个二维数组dist，其中dist[i][j]表示从节点i到节点j的最短路径长度。初始时，dist[i][j]的值为图中节点i到节点j的直接距离，如果两节点之间没有直接边相连，则初始化为无穷大。
动态规划： 对于每一个中间节点k（从1到总节点数），遍历所有节点对(i, j)，并尝试通过中间节点k来优化路径长度。
1
2
3
4
for k from 1 to total_nodes:
for i from 1 to total_nodes:
for j from 1 to total_nodes:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
其中，dist[i][j]表示从节点i到节点j的最短路径长度，dist[i][k]表示从节点i到中间节点k的路径长度，dist[k][j]表示从中间节点k到节点j的路径长度。通过比较当前的最短路径长度和经过中间节点k的路径长度之和，更新最短路径长度。
检测负权环： 遍历所有节点i，如果dist[i][i]小于0，则存在负权环。
输出结果： 最终，dist数组中存储的就是所有节点对之间的最短路径。

Floyd-Warshall算法适用于对图中所有节点对之间的最短路径进行一次性计算，包括检测负权环。它是一种全局最优的算法，但其时间复杂度为O(V^3)，在大规模图上可能不够高效。

代码示例

void floyd(int[][] g) {
    int n = g.length;
    // floyd 基本流程为三层循环: [枚举中转点 - 枚举起点 - 枚举终点] => 松弛操作  
    for (int p = 0; p < n; p++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = Math.min(g[i][j], g[i][p] + g[p][j]);
            }
        }
    }
}

时间复杂度$O(n^3)$；

空间复杂度$O(n^2)$。

判断负权环的方式，运行完Floyd算法之后，若存在i使得$g[i][i]<0$，说明存在负权环。

2.2 Dijkstra算法，适合有向图、无向图，单源最短路，要求无负权边和负权环

Dijkstra算法

适用范围：

Dijkstra算法适用于解决图中单源最短路径的问题，其中边的权重必须为非负值。这是因为Dijkstra算法基于贪心策略，每次选择当前距离最短的节点进行扩展，负权边可能导致不正确的结果。

适用于有向图或无向图。
适用于边权重为非负值的情况。
- 负权边的存在可能导致以下问题：
  1. 无法保证贪心选择的正确性： Dijkstra算法的贪心策略是每次选择当前距离最短的节点来进行扩展。在存在负权边的图中，这样的选择可能导致不正确的结果，因为通过一个负权边可能会使得路径变得更短，而Dijkstra算法无法考虑到这一点。
  2. 可能导致循环计算： 负权边可能导致在图中形成无限循环，从而使得Dijkstra算法陷入无限循环的情况。
  3. 无法处理负权环： 如果存在负权环，那么从该环中的节点出发，通过环形路径返回，路径上的总权重为负值。这种情况下，Dijkstra算法无法正常运行，因为负权环可能导致无限循环的问题。
- 对于负权边的处理，简单的把所有权值都加上某个数是不对的，这样无法保证图中任意一条路径都加上固定的权值。

算法流程：

初始化： 设置源节点的最短路径为0，其他节点的最短路径为正无穷大。创建一个优先队列（最小堆）用于选择当前距离最短的节点。
贪心选择： 从优先队列中选择当前距离最短的节点u，标记节点u为已访问。

注意，标记访问操作可以用visit数组实现，也可以比较dist实现。
松弛操作： 对节点u的所有相邻节点v进行松弛操作，通过比较源节点到达某个节点v的当前最短路径和经过当前边到达该节点v的路径的权重，更新最短路径信息。
1
2
3
4
for each neighbor v of u:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
// 更新优先队列中节点v的距离信息
其中，dist[u]表示从源节点到节点u的当前最短路径长度，weight(u, v)表示边(u, v)的权重。
重复步骤2和3： 重复贪心选择和松弛操作，直到优先队列为空，表示所有可达节点已被访问。
输出结果： 最终，dist数组中存储的就是源节点到各个节点的最短路径。

Dijkstra算法能够高效地求解无负权边的图中的单源最短路径问题。然而，由于其贪心的特性，它无法处理带有负权边的图。在这种情况下，其他算法如Bellman-Ford或SPFA可能更为适用。

代码示例

int[] dijkstra(int x) {
    // 起始先将所有的点标记为「未更新」和「距离为正无穷」
    int[] dist = new int[n];
    Arrays.fill(dist, 0x3f3f3f3f);
    // boolean[] vis = new boolean[n];
    dist[x] = 0;
    // 使用「优先队列」存储所有可用于更新的点
    // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
    PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
    q.add(new int[]{x, 0});
    while (!q.isEmpty()) {
        // 每次从「优先队列」中弹出
        int[] poll = q.poll();
        int u = poll[0], step = poll[1];
        // 如果弹出的点被标记「已更新」，则跳过
        // if (vis[u]) continue;
        if (dist[u] <= step) continue;
        // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
        // vis[u] = true;
        for (int i = head[u]; i != -1; i = next[i]) {
            int j = e[i];
            if (dist[j] <= dist[u] + w[i]) continue;
            dist[j] = dist[u] + w[i];
            q.add(new int[]{j, dist[j]});
        }
    }
    return dist;
}

时间复杂度$O(mlogn)$，m为边数量，n为节点数量；

空间复杂度$O(n+m)$

2.3 Bellman-Ford算法，适合有向图或无向图、负权边、单源最短路，可以判定负权环

适用范围：

Bellman-Ford算法适用于包含负权边的图，并且能够检测图中是否存在负权环。相比于Dijkstra算法，Bellman-Ford更具有通用性，但由于其时间复杂度为O(V * E)（V为节点数，E为边数），在边数较大的情况下可能不如Dijkstra算法高效。

适用于有向图或无向图。
适用于边权重可能为负值的情况。
可以检测图中是否存在负权环。

算法流程：

初始化： 设置源节点的最短路径为0，其他节点的最短路径为正无穷大。
松弛操作： 对每条边进行松弛操作，通过比较源节点到达某个节点的当前最短路径和经过当前边到达该节点的路径的权重，更新最短路径信息。
1
2
3
4
for i from 1 to |V| - 1:
for each edge (u, v) in graph:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
其中，dist[u]表示从源节点到节点u的当前最短路径长度，weight(u, v)表示边(u, v)的权重。
检测负权环： 经过上述操作，如果在第|V|次迭代中仍然可以进行松弛操作，说明存在负权环。这是因为在最短路径中，任意正常的路径至多经过|V|-1个节点。
1
2
3
for each edge (u, v) in graph:
if dist[u] + weight(u, v) < dist[v]:
// 存在负权环
输出结果： 最终，dist数组中存储的就是源节点到各个节点的最短路径长度。

注意：如果图中存在负权环，Bellman-Ford算法会在第|V|次迭代中检测到，并标记这一情况。算法可能不会给出准确的最短路径长度，但可以指示存在负权环。

代码示例

int[] bf(int[][] edges, int x) {
    int[] dist = new int[n];
    // 起始先将所有的点标记为「距离为正无穷」, 只有起点最短距离为 0
    Arrays.fill(dist, 0x3f3f3f3f);
    dist[x] = 0;
    // 有多少个点就迭代多少次
    for (int k = 0; k < n; k++) {
        // 每次都使用上一次迭代的结果，执行松弛操作
        int[] prev = dist.clone();
        for (int[] e : edges) {
            int a = e[0], b = e[1], c = e[2];
            dist[b] = Math.min(dist[b], prev[a] + c);
            dist[a] = Math.min(dist[a], prev[b] + c);
        }
    }
    return dist;
}

时间复杂度$O(m*n)$，m为边数量，n为节点数量；

空间复杂度$O(n+m)$

2.4 SPFA(Shortest Path Faster Algorithm)，和BF算法适用范围一样

适用范围：

SPFA算法适用于包含负权边的图，类似于Bellman-Ford算法，但相对于Bellman-Ford，SPFA使用了队列优化，使得在一般情况下能够更快地收敛。与Bellman-Ford一样，SPFA也能够检测图中是否存在负权环。

适用于有向图或无向图。
适用于边权重可能为负值的情况。
可以检测图中是否存在负权环。

算法流程：

初始化： 设置源节点的最短路径为0，其他节点的最短路径为正无穷大。将源节点加入队列。

松弛操作： 从队列中取出一个节点，对其所有相邻节点进行松弛操作，通过比较源节点到达某个节点的当前最短路径和经过当前边到达该节点的路径的权重，更新最短路径信息。

while 队列不为空:
    取出队首节点 u
    for each edge (u, v) in graph:
        if dist[u] + weight(u, v) < dist[v]:
            dist[v] = dist[u] + weight(u, v)
            if v 不在队列中:
                将节点 v 加入队列

其中，dist[u]表示从源节点到节点u的当前最短路径长度，weight(u, v)表示边(u, v)的权重。

检测负权环： 如果在松弛操作中发现某个节点被更新次数超过了|V|次，则说明存在负权环。
输出结果： 最终，dist数组中存储的就是源节点到各个节点的最短路径长度。

SPFA算法通过使用队列优化，在一般情况下可以比较高效地求解带有负权边的图的最短路径问题。然而，在存在负权环的情况下，SPFA会陷入无限循环，因此对于包含负权环的图，SPFA可能不会给出准确的最短路径。

代码示例

int[] spfa(int x) {
    int[] dist = new int[n];
    boolean[] vis = new boolean[n];
    // 起始先将所有的点标记为「未入队」和「距离为正无穷」
    Arrays.fill(dist, INF);
    // 只有起点最短距离为 0
    dist[x] = 0;
    // 使用「双端队列」存储，存储的是点编号
    Deque<Integer> d = new ArrayDeque<>();
    // 将「源点/起点」进行入队，并标记「已入队」
    d.addLast(x);
    vis[x] = true;
    while (!d.isEmpty()) {
        // 每次从「双端队列」中取出，并标记「未入队」
        int u = d.pollFirst();
        vis[u] = false;
        // 尝试使用该点，更新其他点的最短距离
        // 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] <= dist[u] + w[i]) continue;
            dist[j] = dist[u] + w[i];
            if (vis[j]) continue;
            d.addLast(j);
            vis[j] = true;
        }
    }
    return dist;
}

2.5 Johnson算法

Johnson算法

适用范围：

Johnson算法适用于解决带有负权边的图中的所有节点对之间的最短路径问题，包括检测负权环。Johnson算法结合了Dijkstra算法和Bellman-Ford算法的优势，通过对图进行转换来处理负权边。

适用于有向图或无向图。
适用于边权重可能为负值的情况。
可以检测图中是否存在负权环。

算法流程：

图的转换： 添加一个新的节点（称为超级节点），将新节点与图中的每个节点之间添加一条权重为0的边。这样，新的图中不再包含负权边。
运行Bellman-Ford算法： 使用Bellman-Ford算法计算新图中的超级节点到所有其他节点的最短路径。如果检测到负权环，算法结束，因为对于包含负权环的图，无法得到准确的最短路径。
重新赋权： 对原图中的每条边进行重新赋权，确保边的权重变为原权重加上源节点到目标节点的最短路径长度之差。
1
2
for each edge (u, v) in graph:
weight(u, v) = weight(u, v) + dist[u] - dist[v]
其中，dist[u]和dist[v]分别是超级节点到节点u和v的最短路径长度。
运行Dijkstra算法： 对新图中的每个节点运行Dijkstra算法，计算该节点到所有其他节点的最短路径。
1
2
for each node u:
run Dijkstra algorithm starting from node u to compute dist[u] to all other nodes
恢复最短路径： 将得到的最短路径信息进行还原，考虑超级节点的存在和之前的转换。
输出结果： 最终，得到所有节点对之间的最短路径。

Johnson算法通过将图进行巧妙的转换，综合使用Bellman-Ford算法和Dijkstra算法，能够有效地解决带有负权边的图中的最短路径问题，并且能够检测负权环的存在。

算法模板

1. 存图方式

1.1 邻接矩阵（稠密图）

1.2 邻接表（稀疏图）

1.3 二维列表

2. 最短路算法

2.1 Floyd算法（Floyd-Warshall算法），适合有向图或无向图、负权边、多源最短路，可以判定负权环

适用范围：

算法流程：

代码示例

2.2 Dijkstra算法，适合有向图、无向图，单源最短路，要求无负权边和负权环

适用范围：

算法流程：

代码示例

2.3 Bellman-Ford算法，适合有向图或无向图、负权边、单源最短路，可以判定负权环

适用范围：

算法流程：

代码示例

2.4 SPFA(Shortest Path Faster Algorithm)，和BF算法适用范围一样

适用范围：

算法流程：

代码示例

2.5 Johnson算法

适用范围：

算法流程：

快速选择和排序模板

shutdown3种方式关闭连接的实战抓包分析