前言
定义
- 从某一点出发到某一点的最短路
性质
- 对于边长为正的图：
- 任意两个节点之间的最短路，不会经过重复的节点。
- 任意两个节点之间的最短路，不会经过重复的边。
- 任意两个节点之间的最短路，任意一条的节点数不会超过 \(n\)，边数不会超过 \(n-1\)。
记号
- \(n\) 为图上点的数目，\(m\) 为图上边的数目。
- \(s\) 为最短路的出发点。
- \(D(u)\) 为 \(s\) 点到 \(u\) 点的实际最短路长度。
- \(dis(u)\) 为 \(s\) 点到 \(u\) 的 估计 最短路长度。任何时候有 \(dis(u) \geqslant d(u)\) 。
正文
\(Floyd\) 算法
是用来实现任意两节点之间的最短路的。
复杂度： \(o(n^3)\)
适用于任何图，但不能存在负环。
-
实现：
示例图：
我们定义一个数组 \(f[k][x][y]\)，表示只允许经过节点 \(1 \to k\) 中，节点 \(x\) 到节点 \(y\) 的路径。
那么 \(f[n][x][y]\) 就是节点 \(x\) 到节点 \(y\) 的最短路长度（此时 \(n\) 个点的子图 \(V'\) 即为图 \(V\) 本身）
特殊的点：
\(f[0][x][y]\):从 \(x \to y\) 的边权，或为 \(0\)，或为 \(+\infty\) 。
- \(x\) 与 \(y\) 直接相连：\(x \to y\) 的边权 \(w\)
- \(x\) 与 \(y\) 没有直接相连的边：\(+\infty\)
- \(x = y\) ：\(0\) 。
主要求和式：
f[k][x][y] = f[k-1][x][y] , f[k-1][x][k] + f[k-1][k][y];
（ \(f[k - 1][x][y]\) 为不经过 \(k\) 点的最短路径，\(f[k-1][x][k] + f[k - 1][k][y]\) 为经过 \(k\) 点的最短路径）
需要枚举任意两点的最短路的话，空间和时间复杂度都是 \(o(n^3)\) 。
实现代码如下：
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
}
}
}
优化：空间复杂度：\(o(n^3) \to o(n^2)\)
第一维度对结果无影响，即：
f[k][x][y] = f[k-1][x][y] , f[k-1][x][k] + f[k-1][k][y];
可变为：
f[x][y] = min(f[x][y],f[x][k] + f[k][y]);
实现代码：
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}
\(Bellman ford\)算法
\(Bellman–Ford\) 算法是一种基于松弛（ \(relax\) ）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。
过程
松弛操作：
对于边 \((u , v)\)，对应下面的松弛操作：\(dis(v)=min(dis(v),dis(u)+w(u,v))\) 。
\(bellman ford\) 算法所做的就是对图上的每一条边进行松弛操作，且当一轮循环中没有成功的松弛操作时，算法停止。
时间复杂度：\(o(nm)\)
特殊情况：如果从 \(S\) 点出发，抵达一个负环时，松弛操作会无休止地进行下去。对于最短路存在的图，松弛操作最多只会执行 \(n-1\) 轮，因此如果第 \(n\) 轮循环时仍然存在能松弛的边，说明从 \(S\) 点出发，能够抵达一个负环
负环判断的\(tip\) ：
需要注意的是，以 S 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 S 点出发不能抵达一个负环，而不能说明图上不存在负环。
因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。
实现代码：
struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0;
bool flag; // 判断一轮循环过程中是否发生松弛操作
for (int i = 1; i <= n; i++) {
flag = false;
for (int u = 1; u <= n; u++) {
if (dis[u] == inf) continue;
// 无穷大与常数加减仍然为无穷大
// 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = true;
}
}
}
// 没有可以松弛的边时就停止算法
if (!flag) break;
}
// 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
return flag;
}
列队优化：\(SPFA\)
只有上一次进行过松弛操作，所连接的边，才可能引起下一次的松弛操作。
可以用列队来维护可能引起松弛操作的点。
解释：
如上图，点 \(1\) 为 \(S\) 点，显然只有 \(5\) 和 \(2\) 两点进行了松弛操作，只要用列队存储这两个点，就可以只访问必要的边了。
示例代码：
struct edge {
int v, w;
};
vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;
bool spfa(int n, int s) {
memset(dis, 63, sizeof(dis));
dis[s] = 0, vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop(), vis[u] = 0;
for (auto ed : e[u]) {
int v = ed.v, w = ed.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 记录最短路经过的边数
if (cnt[v] >= n) return false;
// 在不经过负环的情况下，最短路至多经过 n - 1 条边
// 因此如果经过了多于 n 条边，一定说明经过了负环
if (!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return true;
}
\(Dijkstra\) 算法
是一种求解非负权图的单源最短路径的算法
过程
将节点分为两个集合：已确定最短路长度的集合 \((\) 记作 \(S\) 集合 \()\)，和没有确定最短路长度的点集 \((\) 记作 \(T\) 集合 \()\) 。
一开始所有的点属于 \(T\) 集合。
初始化 \(dis(s) = 0\)，其他点的 \(dis\) 均为 \(+\infty\)。
然后重复这些操作：
- 从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中。
- 对那些刚刚被加入 \(S\) 集合的结点的所有出边进行松弛操作 \((Relax)\)。
直到 \(T\) 集合为 \(empty\)
标签：松弛,int,短路,负环,节点,dis From： https://www.cnblogs.com/wyl123ly/p/17755398.html