最短路径笔记
2024-10-11 20:50:03
发布于:浙江
最短路径算法
单源最短路算法
单源 -> 计算一个起点到达其他任意顶点的最短距离的算法 -> 单源最短路算法
多源最短路算法
多源 -> 计算任意顶点到达任意顶点的最短路径算法 -> 多源最短路算法
迪杰斯特拉算法
是 单源最短路算法
松驰
对于某一个顶点进行以下两种操作
- *遍历 : 确定当前这个顶点的最短距离。// 请注意只在迪杰斯特拉当中有这样的效果
- 修改: 修改邻接顶点距离起点的最短距离,当通过松弛的顶点到达相邻顶点的路径距离要小于原先到达该顶点的最短距离则可以修改起点到达该顶点的最短距离。
核心策略
思想: 贪心
依据: 当前顶点如果是距离起点最近的顶点的话,这就意味着没有任意一条路径经过其他顶点后到达该顶点的距离比原先距离还要小。
每次选择距离起点最近的顶点作为下一步要松驰的顶点,松驰的顶点的最短路径被确定,再去寻找下一个最短的顶点再去松弛。
关键代码
我们设定数组dis[x]
代表了顶点x距离起点的最小距离
我们设定数组vis[x]
代表顶点x是否被标记过,true
代表松驰过,false
代表没有
数组mp[x][y]
代表顶点x与y的边的权值
目的: 找到当前距离起点最近的并且没有被松弛过的顶点。
n 代表顶点数量总数 编号为1~n标记
int pos = 0;
for(int i = 1 ; i <= n ; i ++ ) // 遍历所有顶点
{
if(vis[i] == false && dis[pos] > dis[i])
{ // 找到顶点i没有被松弛过并且到达顶点i的距离比到达当前顶点pos的距离更小
pos = i ; // 更新pos为距离更小的顶点i
}
}
- 松弛这个顶点 ,遍历这个顶点
vis[pos] = true ;
- 查找与pos相临的顶点,查看是否需要经过pos到达这些顶点使得他们的最短距离变小
for(int i = 1 ; i <= n ; i ++ )
{
// 如果当前遍历的顶点i与pos存在着边,那么查询
// 经过pos的路径是否更短,是则更新,否则不
if(mp[pos][i] && dis[i] > dis[pos] + mp[pos][i]){
dis[i] = dis[pos] + mp[pos][i] ;
}
}
最终这样的代码需要执行n-1次,对n-1个顶点进行松弛后得到起点到达任意顶点的最短距离。
贝尔曼-福德 斯帕夫
属于单源最短路算法。
注: 任何算法执行的时候都是根据他的算法执行策略(算法思想)执行的,他可以产出一段保证某种性质的数据。
例: 这是一个单源最短路算法,所以他产出的数据是 - 起点到达任意顶点的最短路径。
贝尔曼福德与斯帕夫可以去处理 负权边 的情况。
值得注意的是,迪杰斯塔拉处理不了负权边的情况。
*负权边: 顶点A与顶点B的边的权值为负数的情况。
算法执行策略 - 算法规则
核心思想 : 枚举
对于贝尔曼福德来说,每一个顶点的最短距离是否确定不是根据他是否被松弛过,而是根据他自身的最短路径在本轮松弛当中是否产生变化。
从起点开始进行松弛,假若相临顶点的最短距离发生变化,那么就去遍历发生变化的顶点无关远近。
也就是说,只要还有顶点的最短距离dis[x]
产生变化,那么贝尔曼福德就会无休止的松弛下去。
直到没有任何顶点的最短距离在发生变化后,贝尔曼福德才会停下,此时才得到最短距离答案。
时间复杂度
每一轮对于全部顶点的松弛他可以确定至少一个顶点的最短距离。
贝尔曼福德的三步骤实现
- 松弛所有的顶点,修改所有顶点相临的最短距离
- 检测是否有顶点的最短距离发生改变,如果有,那么回到操作1在执行一遍,如果没有,来到操作3
- 退出循环,得到最短路径数组
dis
struct Node{
int from,to,len ;
}a[100010];
// 边集数组,记录每一条边的起点与终点
// from代表边的起点,to代表边的终点 len代表边的权值
int dis[5005];
bool flag = false ; // 是否需要重新进行全部顶点松弛 false 代表不用 true代表需要
n与m代表顶点数量与边的数量
// 假设顶点编号为1~n,且起点为1
for(int i = 1 ; i <= n ; i ++ )
{
// 最多进行n-1次的松弛遍历
flag = false; // 一开始标记清空为不需要重新松弛遍历
for(int j = 1 ; j <= m ; j ++ )
{
// 枚举每一条边
int to = a[j].to ;
int from = a[j].from;
int len = a[j].len ;
if(dis[from] + len < dis[to]){
//经过这条边的起点from在通过这条边到达顶点to的距离如果小于原先到达to的最短距离那么则更新最短距离
dis[to] = dis[from] + len ;
flag = true ;
// 如果最短距离发生改变,则需要在继续进行遍历
}
}
if(flag == false )break
// 假若不再发生改变则退出
}
贝尔曼福德的缺点
当一个顶点的最短路值发生改变之后,整个矩阵的顶点的最短路径你都需要重新松弛,这样会造成非常多的不必要的顶点松弛,为了避免这样的情况,我们可以去进行优化。
优化点: 将 全部顶点松弛 -> 只对发生改变的顶点进行松弛
需要去解决的问题: 保存发生改变的顶点,针对性的进行松弛。
使用容器,来保存发生改变的顶点。
- 将起点加入queue
- 取出队首进行松弛,如果有顶点的最短路数值发生改变则把顶点加入队列。
- 如果队列不为空,则返回操作2继续执行,否则退出获得最短路数组
dis
。
设定 dis数组都为正无穷的数值,且代表最短距离
设定mp[x][y]保存了顶点x到达顶点y的边的权值
s 代表起点编号
INF 代表正无穷的数值
queue<int> q; // 保存当前发生改变的顶点编号
q.push(s) ; // 压入起点编号
while(!q.empty())
{
// 队列不为空时不停的进行枚举松弛最短距离发生改变的顶点
int fr = q.front() ; // 取出队首顶点松弛
q.pop() ; // 弹出
for(int i = 1 ; i <= n ; i ++ )
{
if(mp[fr][i] != INF && dis[i] > dis[fr] + mp[fr][i]) {
// 假若fr到达i之间存在着一条边,并且通过fr到达i的距离更短 那么修改最短值 并且将i压入到队列当中继续松弛
q.push(i);
dis[i] = dis[fr][i] + mp[fr][i];
}
}
}
出来后就得到了最短距离的数组。
这样优化后的算法,我们把他称之为是SPFA
- 斯帕夫。
这里空空如也
有帮助,赞一个