Appearance
简介
现在给你
松弛操作
使用 邻接矩阵
Floyed 算法
一开始,我们将所有节点全部拨到图外面,然后按
当节点
- 若路径
不经过节点 ,则 ; - 若路径
经过节点 ,则 。
cpp
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
g[k][i][j] = min(g[k - 1][i][j], g[k - 1][i][k] + g[k - 1][k][j]);
实际上,
cpp
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
Floyed
算法适用于任何图,但图中必须存在最短路。时间复杂度为
Bellman-Ford 算法
Bellman-Ford 算法是基于 Floyed 算法 的优化版本,但是只能处理「单源最短路径」:每跑一次 Bellman-Ford,都需要给定源节点
Floyed 枚举节点的效率太低,于是 Bellman-Ford 改为枚举边。
时间复杂度为
cpp
void bellman_ford(int s) {
memset(dis, 0x7f, sizeof dis);
for (int i = 1; i < n; i ++) // 松弛 n - 1 次
for (int j = 1; j <= m; j ++)
dis[to[j]] = min(dis[to[j]], dis[from[j]] + len[j]);
}
判断负权回路
若图中存在长度为负数的 回路,则此回路称为 负权回路(负环)。
有负权回路的图不存在最短路。
在 Bellman-Ford 运行时,如果存在一条路径被松弛了
cpp
bool check(int s) {
memset(dis, 0x7f, sizeof dis);
for (int i = 1; i < n; i ++)
for (int j = 1; j <= m; j ++)
dis[to[j]] = min(dis[to[j]], dis[from[j]] + len[j]);
for (int j = 1; j <= m; j ++)
if (dis[to[j]] > dis[from[j]] + len[j])
return false; // 松弛了 n - 1 次后,还能进行松弛操作,则存在负权回路
return true;
}
SPFA 算法
SPFA 算法是 Bellman-Ford 算法 的队列优化版本。其基本思想是:
- 只有上一次被松弛的节点的出边,才有可能引起下一次的松弛操作。
每次取队首节点,对其出边进行松弛,将松弛到的节点加入队列。
时间复杂度为
cpp
const int N = 1e6;
bool in[N], dis[N]; // in[i]: u 是否在栈中
struct node {
int val, len;
};
vector<int> g[N]; // g[u]: u 节点的邻接节点集合
void spfa(int s) {
memset(in, false, sizeof in);
memset(dis, 0x7f, sizeof dis);
dis[s] = 0;
queue<int> Q;
Q.push(s), in[s] = true;
while (!Q.empty()) {
int u = Q.front();
Q.pop(), in[u] = false;
for (int i = 0; i < (int) g[u].size(); i ++) {
int v = g[u][i].val;
int d = g[u][i].len;
if (dis[v] > dis[u] + d) {
dis[v] = dis[u] + d;
if (!in[v]) { // 已经在栈里的节点没必要再进栈一次
Q.push(v), in[v] = true;
}
}
}
}
}
判断负权回路
cpp
const int N = 1e6;
bool in[N], dis[N], relax[N]; // relax[u]: dis[u] 被松弛的次数
struct node {
int val, len;
};
vector<int> g[N];
bool spfa(int s) {
memset(in, false, sizeof in);
memset(dis, 0x7f, sizeof dis);
dis[s] = 0;
queue<int> Q;
Q.push(s), in[s] = true;
while (!Q.empty()) {
int u = Q.front();
Q.pop(), in[u] = false;
for (int i = 0; i < (int) g[u].size(); i ++) {
int v = g[u][i].val;
int d = g[u][i].len;
if (dis[v] > dis[u] + d) {
dis[v] = dis[u] + d;
if (++ relax[v] >= n) // 松弛了 n 次及以上,存在负权回路
return false;
if (!in[v]) {
Q.push(v), in[v] = true;
}
}
}
}
return true;
}
Dijkstra 算法
从节点
重复以下操作直到第二个集合中没有节点:
- 松弛刚加入第一个集合的节点的所有出边;
- 从第二个集合中,选取
值最小的节点,加入第一个集合。
只能处理单源最短路径,不能处理负权路径。时间复杂度为
cpp
const int N = 1e6;
int avl[N], dis[N];
void dijkstra(int s) {
memset(avl, true, sizeof avl);
memset(dis, 0x7f, sizeof dis);
dis[s] = 0;
for (int i = 1; i <= n; i ++) {
int minn = INF, minp = 0;
for (int j = 1; j <= n; j ++)
if (avl[j] && dis[j] < minn)
minn = dis[j], minp = j;
if (!minp) continue;
avl[minp] = false;
for (int j = 1; j <= n; j ++)
if (avl[j] && dis[j] > minn + g[minp][j])
dis[j] = minn + g[minp][j];
}
}