最短路问题
- 单源最短路
- 一般n和m都很大（10万或以上）
- 所有边权都是正数
- 朴素Dijkstra算法
- 堆优化版的Dijkstra算法
- 存在负权边
- Bellman–Ford
- Shortest Path Faster Algorithm (SPFA)
- 多源汇最短路
- 一般n很小（200左右），m很大（10万）
- Floyd算法
- 考察
- 将实际问题抽象成一个在图中求最短路的问题
- 建图，定义点和边
单源最短路
- 只有一个起点，求到其他所有点的最短路距离
朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
- 边权均为正数
- 因为Dijsktra是基于贪心来做的，每次从局部情况来确定全局最优解，这只有在边权均为正数时成立
- 思路
dist[1] = 0.dist[i] = INF //1到1距离为0，其他点到1距离为正无穷
for i in 1 ~ n:
t <- 不在s中的到1距离最短的点
//这一步是贪心，认为此时t已经找到最短路径了。因为在所有边权都为正数时，路径一定越走越长
//如果存在负权边，就不成立
s <- t
用t更新其他点到1的距离
if dist[x] > dist[t] + w
then dist[x] = dist[t] + w
时间复杂是 $O(n^2+m)$ , $n$ 表示点数，$m$ 表示边数
朴素算法时间复杂度受边数影响较小。适合边稠密型的图
稠密：$m = n^2$
模板
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ ) //循环n-1次,因为最后一个点不用入s
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ ) //循环n次
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ ) //遍历所有的边，总共遍历m次
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
- 朴素算法中 $n^2$ 的操作是找最小距离，因此可以用小根堆优化
时间复杂度 $O(mlogn)$, $n$ 表示点数，$m$ 表示边数
当边稠密时，时间复杂度接近 $O(n^2logn)$ ,比朴素算法要高，因此不适合边稠密的图
模板
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
/*
题目中堆的更新是直接将新PII加入到堆中，因此一个点在堆中可能会重复出现，
所以要判断该点是否已经取到最短距离
如果是手写堆就不用加st数组，因为每次更新堆都是直接将堆中的数据进行修改，
所以堆中不会有重复的点，也不会有已经取得最小距离的点
*/
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i]) //循环m次，堆中修改一个数时间复杂度是logn
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路
- 存在负权边
- 思路：
for n次
for 所有边a,b,w
dist[b] = min(dist[b],dist[a] + w);
- 遍历完之后，所有dist[b]满足 $dist[b]\leq dist[a]+w$
- 如果图中存在负权圈（负环），即圈的长度小于0，则不存在最短路（因为可以在圈里无限绕，长度可以达到负无穷）
- 判断是否存在负权圈
- 最外层循环，循环k次后的dist[i]意味着从1出发走不超过k条边到达i的最短路径长。
- 当 $k=n$ ，说明1到i的最短路径是一条经过边数超过n的路径，
- 由抽屉原理可知，该路径中一定有点被重复经过，因此存在负权圈
- 判断是否存在负权圈
时间复杂度 $O(nm)$, $n$ 表示点数，$m$ 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
模板
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
//这里在更新时涉及到串联的问题
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
- 串联问题 & backup数组
if (dist[b] > dist[a] + w)这里dist[a]表示的应该是在 $k-1$ 条边之内1到a的最短距离- 但如果出现了下图这种情况
- 很明显，如果只能走一步，那1到3的距离就是3，但是算法在遍历每一条边来更新dist时，如果23边在12边之后被遍历到，那么在遍历23边，执行
if (dist[b] > dist[a] + w)时，dist[a]表示的就是1步之内1到a的最短路径长，这时更新的dist[b]表示的就是2步的1到b的最短路径长。 - 上述就是串联问题。在单纯求最短路的情况下可以不考虑串联，但如果求在 $k$ 步之内的最短距离，就要避免串联
- 方法：建立一个backup数组，每次循环所有边之前将未被更新的dist备份进backup，然后用将判断语句替换为
if (dist[b] > backup[a] + w),就可以避免串联
- 方法：建立一个backup数组，每次循环所有边之前将未被更新的dist备份进backup，然后用将判断语句替换为
- 代码
spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路
- 只要没有负环，推荐用spfa
- 优化
dist[b] = min(dist[b],dist[a] + w)每次更新时，如果dist[a]不变小，那么这句语句在执行时就没有意义，只会浪费时间- 此处可以通过bfs优化(图用邻接表存)
- 思路
queue存储所有dist变小的点
queue <- 1
while queue不空
t <- queue.head
queue.pop
更新一下t的所有出边 t <- b
if b not in queue
queue <- b
时间复杂度 平均情况下 $O(m)$，最坏情况下 $O(nm)$, $n$ 表示点数，$m$ 表示边数
- 理论上可以替代Dijkstra，但是做题时容易被卡时间复杂度，所以一般Dijkstra还是不用spfa
- 如何优雅地卡spfa,一位大佬写的博客
模板
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
//之后判断一下，如果返回参数大于某个很大的数（如0x3f3f3f3f / 2），就说明不存在最短路
}
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 $O(nm)$, $n$ 表示点数，$m$ 表示边数
模板
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
多源汇最短路
- 有多个起点（源点）和终点（汇点），每次给出一个询问，求询问中两个点的最短路
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
- 基于动态规划
d[k,i,j]表示从i经过1~k里的点(按集合的定义一定要过k)到j的最短距离d[k,i,j] = d[k - 1,i,k] + d[k - 1,k,j]
时间复杂度是 $O(n^3)$, $n$ 表示点数
模板
初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
作者：yxc
链接：https://www.acwing.com/blog/content/405/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
wow 好帅
大佬学多久啊
两天看一节课 :sob: 😭