各类最短路模板

2024-07-16 09:11| 来源: 网络整理| 查看: 265

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

1. 存图方式1.1 邻接矩阵（稠密图）

使用二维矩阵来存图。

1234567// 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 邻接表（稀疏图）

即链式前向星。

1234567891011121314int[] 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 二维列表12345678910111213List[] 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来优化路径长度。

1234for 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)，在大规模图上可能不够高效。

代码示例1234567891011void 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]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]

【本文地址】

公司简介

联系我们