最短路算法
2024-08-15 15:52:38
发布于：浙江
最短路算法
解决的问题
常常用于去解决在一个图当中，从一个顶点出发到达另一个顶点的最小路径权值总和求值。
前置知识点
- 图的基础知识
- 邻接矩阵/邻接表
- 贪心/枚举
最短路算法
-
单源最短路
- 从一个固定的起点出发，到达图上任意顶点的最短距离，如果我们将起点的顶点编号设置为,将任意顶点的编号设置为，那么我们所求就是的最短路径。
-
多源最短路
- 从任意一个起点出发，到达图上任意顶点的最短距离，我们将顶点数量最大设定为，那么多源最短路所求的就是的最短路径。
-
实现方式
- 数组与其含义:我们通常会定义一个的数组，使顶点编号作为其数组的对应下标，来保存其中号顶点的之间的最短距离。
- **数组的定义差异:**根据单源最短路和多源最短路的差异性(则起点是否为固定)，我们可以将数组设置成（单源最短路）或(多源最短路)。
- 单源最短路由于起点是固定的，因此只需要一个下标来表示终点的位置即可组成关系，保存单个起点的最短路径权值总和。
- 而多源最短路由于起点不固定,所以我们需要两个下标来组成关系，保存其两个顶点之间最短路径的权值总和。
松弛
松弛操作是所有最短路算法的核心思想，掌握了松弛，那么最短路算法的种类再多，也可以非常快速地理解。
操作方式:松弛就是以某一个顶点作为中转站，更新与这个顶点相邻的其他顶点的最短路径数值。 (我们把这种操作，称之为对于中转站顶点的松弛)。
多源最短路表达方式： 设定为当前路径起点，为当前的路径终点,为当前我们需要去松弛的顶点。
:
单源最短路表达方式: 在起点已经固定了的情况下，我们设置点为当前路径终点，为当前我们需要去松弛的顶点，已知保存了起点到达目前的最短距离，保存了起点到达的最短距离,表示顶点到达边的权值，那么表达式为
: =
Floyd
核心思路
- 枚举任意一个顶点来作为即将要松弛的顶点。
- 遍历当前可以前往松弛顶点的其他顶点，作为起点。
- 遍历松弛顶点可以前往的顶点作为终点。
- 比较原先起点到终点的最短距离 与经过松弛顶点的距离作比较，取最小值更新最短距离。
因而，根据核心思路的先后顺序，可得出核心代码
for(int k = 1 ; k <= n ; k ++ ) // 先有要松弛的顶点
{
for(int i = 1 ; i <= n ; i ++ ) // 再有可以到达松弛的起点
{
for(int j = 1 ; j <= n ; j ++ ) // 再有可以到达的终点
{
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); // 比较取最小值。
}
}
}
Dij
核心思想
由于是单源最短路算法，因此起点为固定的顶点。计算思维是根据贪心思想拓展而来，贪心策略为:遍历次，每次选择距离起点最近的未遍历顶点作为下一个松弛的顶点，跟边的个数无关。因此Dij算法时间复杂度大多时候直接跟顶点总数挂钩。
无法处理负权边
#include<bits/stdc++.h>
using namespace std;
bool vis[MAXN];
struct Node{
int v,w; //终点与权值
};
vector<Node> G[MAXN];
int dis[MAXN];
void dj()// O(n^2 + n * m)
{
memset(dis,0x3f3f3f3f3f,sizeof dis); // 其他初始化为正无穷
memset(vis,0,sizeof vis);
dis[start] = 0 ; // 起点到达起点最短距离未为0
for(int i = 1 ; i <= n ; i ++ ) // O(n)
{ // 松弛n个顶点
int pos = 0 ;// 储存下一个要松弛的顶点
for(int j = 1 ; j <= n ; j ++ )// O(n)
{
// 查找下一个距离起点最近且未被遍历过的顶点
if(!vis[j] && dis[pos] > dis[j]) pos = j ;
}
if(!pos)return ;
vis[pos] = true ;
for(int j = 0 ; j < G[pos].size() ; j ++ ) O(m)
{
// 遍历这个顶点的邻居，更新到达他们的最短路径
int next_pos = G[pos][j].v; // 获取邻居顶点
dis[next_pos] = min(dis[next_pos],dis[pos] + G[pos][j].w);
// 比较是原来更快还是松弛后更快
}
}
}
int main()
{
return 0;
}
Dij优化
- 在Dij当中，我们为了寻找距离起点最近的顶点，通常需要使用for循环进行时间复杂度为的暴力枚举，这样的做法效率实在是过于低下，我们可以思考，有没有有一种容器，可以自动的将此时权值最小的顶点顶出来让我们自己使用呢？
- priority_queue 优先队列，优先队列可以设定排序规则，使其里面的元素按照某一种数值进行升序或者降序的排序，最值会作为队首拿出，每一次拿出插入的时间复杂度为
- 假如，我们使用priority_queue来对搜索最近顶点的for循环进行替换，时间复杂度也就可以从
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
struct Node{
int v,w;
friend bool operator < (Node a,Node b){ // 默认按照这种来进行排序
return a.w > b.w ; // 满足条件的偏向队尾 不满足偏向队首
}
};
vector<Node> G[MAXN];
int n,m,s;
int dis[MAXN];
bool vis[MAXN];
void dij()
{
for(int i = 0 ; i < MAXN ; i ++)dis[i] = 1e9+7;
dis[s] = 0 ;
priority_queue<Node> q;
q.push({s,0});
while(!q.empty())//优先队列最终一定会压入所有能松弛的顶点 为空则代表遍历完毕 不为空继续
{
Node fr = q.top(); // 取出此时距离起点最近的顶点
q.pop();
vis[fr.v] = true; // 标记已经遍历过了
// 拿去松弛
int pos = fr.v;
for(int i = 0 ; i < G[pos].size() ; i ++ )
{
int next_pos = G[pos][i].v;
dis[next_pos] = min(dis[next_pos],dis[pos] + G[pos][i].w);
if(!vis[next_pos])
{
q.push({next_pos,dis[next_pos]});
}
}
}
}
int main()
{
cin >> n >> m >> s;
while(m--)
{
int u,v,w;
cin >> u >> v >> w;
G[u].push_back({v,w});
}
dij();
for(int i = 1 ; i <= n ; i ++ )
dis[i] == 1e9+7 ? cout <<"-1" << " " :
cout << dis[i] << " ";
return 0;
}
Bellman - Ford最短路算法
单源最短路
核心思想:
枚举所有的边求最终的最小权值，准确的来说是枚举所有顶点的所有边，无视先后顺序，每当一次枚举的时候dis数组发生了改变，则进行下一次从头枚举，直到dis数组不再改变则结束。将dis数组不发生改变的这样的行为视为是枚举的终点，在这个终点为达到之前，会不停的从头遍历每一条边。
示范代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
struct Node{
int from,to,len ; // 起点终点权值
}a[MAXN];
int cnt ; // 保存边数量
void add(int from,int to,int len){ // 增加一条边加到边集数组当中
a[cnt].from = from;
a[cnt].to = to;
a[cnt++].len = len ;
}
int dis[MAXN];
int main()
{
int n,m,s,t; //n个顶点m条边s起点t终点
cin >> n >> m >> s >> t;
for(int i = 0 ; i < MAXN ; i ++ )dis[i] = 1e9+7;
dis[s] = 0;
while(m--)
{
int u,v,w;
cin >> u >> v >> w;
add(u,v,w); // 保存边
}
for(int k = 0 ; k < n ; k ++ )
{
bool flag = true; // 标记当前是否发生改变
// 贝尔曼福德最终能遍历的次数不会超过n-1次，假若在第n次还在变换则说明具有负环
for(int i = 0 ; i < cnt ; i ++ )
{
// 遍历所有的边进行松弛
int from = a[i].from;
int to = a[i].to;
int len = a[i].len;
if(dis[to] > dis[from] + len){
flag = false;
dis[to] = dis[from] + len ; // 假若原先行走的数值大于松弛的数值则更新
}
}
if(flag)break; // 没发生改变停止Bellman-ford
}
for(int i = 1 ; i <= n ; i ++)cout << dis[i] << " " ;
return 0;
}
SPFA
核心思想: BellMan-Ford算法在运行的过程当中，由于会对不会发生变化的边进行重复无意义的松弛 ，因此我们优化的策略就可以从这里入手，由 全部松弛 -> 只松弛可能产生变化的边，从而降低时间复杂度。
核心做法: 队列来维护可能产生的顶点队列，在松弛的过程当中，不停的加入产生了变化且没有进入过队列的边，从而进行继续松弛，直到队列为空为止。
代码框架
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+7;
struct Node{
int v,w;
};
vector<Node> G[MAXN]; // 邻接表
int dis[MAXN];
bool vis[MAXN];
int s;
void Spfa()
{
dis[s] = 0; // 起点初始值为0
vis[s] = true; // 标记为使用过了
queue<int> q;
q.push(s); // 压入起点
while(!q.empty()) // 队列不为空时意味着还有顶点在更新
{
int pos = q.front();
q.pop();
vis[pos] = false; // 当前顶点取出，那么假如被更新了，可以再次
//加入队列，因此释放
for(int i = 0 ; i < G[pos].size() ; i ++ )
{
// 对于相邻边进行松弛
int next_pos = G[pos][i].v;
int len = G[pos][i].w;
if(dis[next_pos] > dis[pos] + len) {
dis[next_pos] = dis[pos] + len ;
if(!vis[next_pos]){
// 当前顶点没有被标记过且被更新了
q.push(next_pos);
vis[next_pos] = true;// 放入队列再次进行遍历。
}
}
}
}
}
int main()
{
/*
存图过程
*/
Spfa();
return 0;
}
全部评论 27
Yuilice太棒啦~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2024-08-14 来自 浙江
0
有帮助，赞一个