最短路问题
常见的最短路问题可以分成两大类
- 单源最短路
- 多源汇最短路在最短路问题中,源点 也就是 起点,汇点 也就是 终点
单源最短路
单源最短路,指的是求一个点,到其他所有点的最短距离。(起点是固定的,单一的)
单元最短路问题又分成两种(n:点数,m:边数):
- 所有边权都是正数
- 朴素Dijkstra O(n2)
- 堆优化Dijkstra O(mlogn)两者孰优孰劣,取决于图的疏密程度(取决于点数n,与边数m的大小关系)。当是稀疏图(n和m是同一级别)时,可能堆优化版的Dijkstra会好一些。当是稠密图时(m和n2是同一级别),使用朴素Dijkstra会好一些。
- 存在负权边
- Bellman-Ford O(mn)
- SPFA 一般:O(m),最坏:O(mn)
多源汇最短路
- Floyd O(n3)
最短路问题的核心在于,把问题抽象成一个最短路问题,并建图。图论相关的问题,不侧重于算法原理,而侧重于对问题的抽象。
Dijkstra基于贪心,Floyd基于动态规划,Bellman-Ford基于离散数学。
算法的选用:通常来说,单源最短路的,如果没有负权重的边,用Dijkstra,有负权重边的,通常用SPFA,极少数用Bellman-Ford;多源最短路的,用Floyd
算法思路
朴素Dijkstra
用一个集合s来存放最短距离已经确定的点。
- 初始化
dist
,dist[1] = 0, 其他dist[i] = INF
- 循环n次:每次从距离已知的点中,选取一个不在s集合中,且距离最短的点t(这一步可以用小根堆来优化),把t加入到集合s中,遍历t的所有出边,更新这些出边所连接的点的距离。
- 当所有点都都被加入到s中,表示全部点的最短距离都已经确定完毕
朴素Dijkstra对应稠密图,因此用邻接矩阵来存储
算法模板
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 ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化Dijkstra
堆可以自己手写(用数组模拟),也可以使用现成的(C++的STL提供了priority_queue,Java的JDK中提供了PriorityQueue)特别注意,插入堆的操作,由于更新距离时,可能对一些距离已知的点进行更新(更新为更小的距离),此时不能因为这个点已经在堆中就不进行插入了,因为其距离已经变了,堆中原有的节点已经无效了,按理说,应该修改堆中对应节点的距离值,然后做调整,实际上,可以直接插入一个新的节点(此时对于同一个节点,堆中有两份),但没有关系,堆中的重复节点不会影响最终的结果。
算法模板
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;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Bellman-Ford
算法思路
- 循环n次
- 每次循环,遍历图中所有的边。对每条边(a, b, w),(指的是从a点到b点,权重是w的一条边)更新d[b] = min(d[b], d[a] + w)
(可以定义一个类,或者C++里面的结构体,存储a,b,w。表示存在一条边a点指向b点,权重为w)。则遍历所有边时,只要遍历全部的结构体数组即可
循环的次数的含义:假设循环了k次,则表示,从起点,经过不超过k条边,走到每个点的最短距离。
该算法能够保证,在循环n次后,对所有的边(a, b, w)
,都满足d[b] <= d[a] + w
。这个不等式被称为三角不等式。上面的更新操作称为松弛操作。
该算法适用于有负权边的情况,注意:如果有负权环的话,最短路就不一定存在了。
该算法可以求出来,图中是否存在负权回路。如果迭代到第n次,还会进行更新,则说明存在一条最短路,路径上有n条边,n条边则需要n + 1个点,而由于图中一共只有n个点,所以这n + 1个点中一定有2个点是同一个点,则说明这条路径上有环;有环,并且此次进行了更新,说明这个环的权重是负的(只有更新后总的距离变得更小,才会执行更新)。
但求解负权回路,通常用SPFA算法,而不用Bellman-Ford算法,因为前者的时间复杂度更低。
代码模板
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];
}
SPFA
若要使用SPFA算法,一定要求图中不能有负权回路。只要图中没有负权回路,都可以用SPFA,这个算法的限制是比较小的。
SPFA其实是对Bellman-Ford的一种优化。
它优化的是这一步:d[b] = min(d[b], d[a] + w)
我们观察可以发现,只有当d[a]
变小了,才会在下一轮循环中更新d[b]
考虑用BFS来做优化。用一个队列queue,来存放距离变小的节点。(当图中存在负权回路时,队列永远都不会为空,因为总是会存在某个点,在一次松弛操作后,距离变小)(和Dijkstra很像)
代码模板
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;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
SPFA的好处:
能解决无负权边的问题,也能解决有负权边的问题,并且效率还比较高。但是当需要求在走不超过k条边的最短路问题上,就只能用Bellman-Ford算法了。
Floyd
求解多源汇最短路问题,也能处理边权为负数的情况,但是无法处理存在负权回路的情况。
使用邻接矩阵来存储图。初始使用d[i][j]来存储这个图,存储所有的边
算法思路:三层循环
算法模板
初始化:
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]);
}
循环结束后,d[i][j]存的就是点i到j的最短距离。
原理是基于动态规划(具体原理在后续的动态规划章节再做详解)。
其状态表示是:d(k, i, j),从点i,只经过1 ~ k这些中间点,到达点j的最短距离
标签:图论,第三章,int,短路,存储,算法,搜索,dist,号点 From: https://www.cnblogs.com/chenjq12/p/17115014.html