最短路问题

最短路

这篇会讲基础的最短路问题 讲Floyd算法 Johnson算法 Dijkstra算法 Bellman-Ford / SPFA 算法最后比较一下

目录

• 1.什么是最短路
• 2.Floyd算法
• 3.Bellman-Ford / SPFA
• 4.Dijkstra算法
• 5.Johnson算法

一. 什么是最短路?

最短路问题是图论中的经典问题: 给一个带权图 要求寻找两点间权值之和最小的路径 最短路分为两类 : 单源最短路: 求得一个指定源点到所有其他结点的最短路 全源最短路: 求得图中任意两个结点之间的最短路

由定义 我们易得最短路的几条性质: 1. 有最短路的图 一定不是带负环的图 (无限经过负环左脚踩右脚上天) 2. 对于一个图 最短路径不会经过重复节点 (若存在重复节点 由1得 一定多的是一条正权边 故不是最短路) 3.最短路有最优子结构 最短路径中任意两点的最短路径一定在原最短路径上 (如果结点 x 和 y 在某条最短路 s->t 上 那么 x->y 在这条路径上的部分就是 x 到 y 的最短路. 否则, 若存在一条更短的 x->y 路径 替换进去会得到一条更短的 s->t 路径 矛盾)

从这个第三条来拓展 我们就得出了第一种计算最短路的方法:

二. 最短路算法

1. Floyd算法 (全源最短路)

核心思路: 动态规划 逐个引入两点间的中间结点, 看通过这个结点能否让某两点之间的路径变短 初始化

f[i][i] = 0;
有边: f[u][v] = w;
无边: f[i][j] = INF;

实现 定义一个数组f[x][y] : x到y的最短路长度

for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]); //尝试利用k使路径变短
}
}
}

x到y的最短路 计算是否加入k节点 加入: 走k (x到k的最短路+k到y的最短路) 不加入: 不走k 沿用以前的结果

时间复杂度 O(n³) 可用于有向/无向 正权/负权图 优点 : 简单 缺点 : 太慢

2.1 Bellman-Ford 算法 (单源最短路)

核心思路 : 松弛 单源最短路数组 dis[x] 表示从单个节点到 x 的最短路 松弛操作: 对于任意一条边 u->v 若 dis[u]+w(u->v) 小于 dis[v] 那么更新我的 dis[v] 即每次更新最短路

Bellman-Ford算法 : 对所有边进行 n-1轮 松弛 (最长的最短路包含n-1条边 经过n-1次松弛后一定能找到最短路) 根据这一条推论 我们可以利用Bellman-Ford找负环 : 若我们在第 n 轮还在松弛 证明这个图没有最短路 证明这个图有负环 这里main函数存边 因为是针对边的遍历

void bellmanford(int start) {
memset(dis, 0x3f, sizeof dis); // 默认到任意节点距离为最大值
dis[start] = 0;
for (int i = 1; i <= n; i++) {
bool ifrelax = 0;
for (auto e:edges) { // edges是边数组
if (dis[e.u] == INF) continue; // 原点到不了
if (dis[e.v] > dis[e.u]+e.w) {
dis[e.v] = dis[e.u]+e.w;
ifrelax = 1;
}
}
if (!ifrelax) break; // 未发生松弛 证明当前已经是最短路了
if (i == n) iffuhuan = 1; // 到了第n轮还在松弛 一定有负环
}

}

时间复杂度 O(n*m) 可用于有向/无向 有负权图 可检测负环

2.2 Bellman_Ford优化 – SPFA

Bellman-Ford对于每条边都无差别判断了是否要松弛 明显这很多余 SPFA用队列维护了哪些结点可能引起松弛

如何检测负环 记录每个结点最短路径经过的边数 cnt[v] , 正常情况下, 最短路最多经过 n-1 条边 若 cnt[v] >= n 明显 经过了负环

void spfa(int start) {
memset(dis, 0x3f, sizeof dis);
dis[start] = 0;
vis[start] = 1; // 记录start在不在队列中
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0; // u 不在队列中
for (int e:edges[u]) { // edges[u] 为u的出边数组
int v = e.v, w = e.w;
if (dis[v] > dis[u]+w) {
dis[v] = dis[u]+w; // 松弛
cnt[v] = cnt[u] + 1; // 统计经过边数
// 通过了u的v节点 边的个数为通过u的边数加1
if (cnt[v] >= n) iffuhuan = 1; // 存在负环
if (!vis[v]) {// v不在队列中 入队
q.push(v);
vis[v] = 1;
}
}
}
}

}

时间复杂度 最坏O(n*m) 大部分时候优于原始Bellman-Ford 可用于有向/无向 有负权图 可检测负环

3. Dijkstra 算法 (单源最短路)

核心思想: 贪心 (十分朴素对吧) 每次从尚未确定最短路的结点中, 选择距离源点最近的结点, 将其标记为"已确定", 然后用它去松弛所有邻居 这个贪心思路仅适用于无负权边的图 在正权边图中, 对于没确定的一个离源点最近的节点 u 即边su最小 明显地 没有任何一个点能比 u 还离源点近 除非存在负权边 举个例子 若存在负权边 按照原贪心思路 距离1最近的节点 u 为节点3 最短路为1 但如果有负权边的加入 最短路明显是1->2->3为-1 故这个贪心思路不适用于带负权边的图

每次要找最小边 故加入优先队列优化 每次取出最小值

void dijkstra(int start) {
memset(dis, 0x3f, sizeof dis); // dis数组同bellmanford用法
dis[start] = 0;
priority_queue<pair<int, int>, vector<...>, greater<...>> q;
q.push({0, start}); // first存距离 second存节点 使优先队列按距离排序
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto e:g[u]) { //g是邻接表
int v = g.v, w = g.w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
}

时间复杂度 O(mlogn) 边权不能为负 这种算法也是最常用的单源最短路算法 效率高且思路清晰

4. Johnson 算法 (全源最短路)

这个算法是结合Bellman-Ford 和 Dijkstra 的思想高效求解全源最短路 想法 目标: 在一个可能有负权边的图上, 求任意两点之间的最短路(全源最短路)

所以 现在的问题在于 能不能对负权边进行操作 让它变成非负, 然后跑n遍Dijkstra, 得出全源最短路 给每条边都加上一个很大的数: 明显错误 最短路等于最短路径的权值加经过边乘以大数

Johnson 算法: 给每个结点赋予一个"势能" h[v] 把边权 w(u,v) 改造成 w’(u,v) = w(u,v) + h[u] – h[v] 把每条路径累加 发现最后一项被消了, 于是 从起点 s 到终点 t 的最短路为 sum(w’) = sum(w) + h[s] – h[t] 故, 对于同一个起点 s 和同一个终点 t 无论走哪条路径 改造后总和sum (w’)与改造前总和sum(w)的差值永远是固定的为h[s] – h[t]

接下来就是怎么找h[v], 使得所有新边权 w’(u,v) 都大于等于 0 了

跑完之后 我们得到了 S 到所有节点的 dis[v], 明显, dis[v]一定 <= 0 (最短路要么直接走 0 的权边 要么还有负权边走一走)

johnson算法核心思想: 重新定义边的权值 然后跑n遍dijkstra

void bellman_ford() { // 核心代码基本同上
memset(dis, 0, sizeof dis);
// 我们定义的源点S到所有点距离为0 等价于dis全0
for (int i = 1; i <= n; i++) {
bool ifrelax = 0;
for (auto e : edges) {
if (dis[e.v] > dis[e.u] + e.w) {
dis[e.v] = dis[e.u] + e.w;
ifrelax = 1;
}
}
if (!ifrelax) break;
if (i == n) iffuhuan = 1;
}
}

void dijkstra(int start) {
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
priority_queue<pair<int,int>, vector<...>, greater<...> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto e:g[u]) { // g是邻接表
int v = e.v, w = e.w;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
void johnson() {
// 求势能
bellman_ford();
if (iffuhuan) {
// 存在负环
return;
}

// 改权 建新图
for (auto e:edges) {
int new_w = e.w + dis[e.u] – dis[e.v]; // dis等价于h数组
g[e.u].push_back({e.v, new_w});
}

// 对每个源点跑dijkstra, 并还原真实距离
for (int s = 1; s <= n; s++) {
dijkstra(s);
for (int t = 1; t <= n; t++) {
if (dist[t] == INF) printf(s->t = INF);
else printf(s->t = dis[t] – h[s] + h[t]);
}
}
}

总结

最短路问题是图论里很常见的问题 这几个都很常用