? 优质资源分享 ?
学习路线指引(点击解锁) | 知识定位 | 人群定位 |
---|---|---|
? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。 |
?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
图的最短路径问题 详细分解版
1.图的最短路径问题分类
2.单源最短路问题
2.1边权值都是正数情况
2.1.1 朴素Dijstra算法
算法思想:每次从未被确定最短距离的结点中找出距离起点最小值的结点,加入集合s中,并用该结点更新其他未被确定最短路径值得结点路径。直到最终全部节点的最短路径值都计算出,此时集合s为所有结点集合。
#include
using namespace std;
const int N = 510;
int g[N][N];//稠密图,邻接矩阵存储
int st[N];//是否被访问过,即是否在s集合中
int dist[N];//记录每个点到起点的距离
int n,m;
//返回编号为n的结点到1号结点的最短路径
int dijstra(){
memset(dist,0x3f,sizeof dist);//将距离初始化为无穷大
dist[1]=0;//1号结点距离初始化为0
for(int i=0;i//n轮循环,每次找出一个结点,加入s集合,并用其更新其他节点dist数组。必须有n轮循环,因为要更新dist数组
int t=-1;
for(int j=1;j<=n;j++){//循环找出当前距离起始的1号结点最近,且未加入s的结点
if(!st[j]&&(t==-1||dist[j]true;//将该结点加入s数组
for(int j=1;j<=n;j++){//循环更新其他节点距离
if(!st[j]){
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;//如果dist[n]未被更新,说明其不可达
return dist[n];
}
int main(){
memset(g,0x3f,sizeof g);//初始化结点间的距离为无穷大
cin>>n>>m;//输入数据包含n个结点,m条边
int a,b,c;
while(m--){
cin>>a>>b>>c;//输入m条边,输入数据存在自环和重边,取最小值即可
g[a][b]=min(g[a][b],c);
}
cout<<dijstra()<return 0;
}
算法分析:算法包含两轮循环,时间复杂度为O(n2)O(n2)O(n^2)
2.1.2 堆优化的Dijstra算法
优化思想:朴素Dijstra算法每次都要找出当前距离起点最近的结点,加入集合s中。我们可以使用堆来维护结点距离起点的距离,省去一重循环。
//稀疏图的dijstra
#include
using namespace std;
const int N = 1.5e5+10;
int e[N],ne[N],w[N],h[N],idx;//稀疏图,采用邻接表存储
int n,m;//n个结点,m条边
int dist[N];//距离数组
bool st[N];//是否访问过,即s集合标记
typedef pair<int, int> PII;//使用堆自动排序,pair的first为距离,second为编号
void add(int a,int b,int c){//添加结点a->b的边,权值为c
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue,greater> q;//声明小根堆
q.push({0,1});//1号结点加入队列
while(!q.empty()){
PII t=q.top();
q.pop();
int distance=t.first,x=t.second;
if(st[x]) continue;//距离已经确定,跳过
st[x]=true;
for(int i=h[x];i!=-1;i=ne[i]){
int j=e[i];
if(dist[x]+w[i]push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
cin>>n>>m;
int a,b,c;
memset(h,-1,sizeof h);
while(m--){
cin>>a>>b>>c;
add(a,b,c);
}
cout<<dijstra()<return 0;
}
算法分析:
时间复杂度:每次找到最小距离的点沿着边更新其他的点,若dist[j] > distance + w[i]
,表示可以更新dist[j]
,更新后再把j
点和对应的距离放入小根堆中。由于点的个数是n
,边的个数是m
,在极限情况下(稠密图m=n∗n(n−1)2m=n∗n(n−1)2m=\frac{n*n(n-1)}{2})最多可以更新m
回,每一回最多可以更新n2n2n^2个点(严格上是n - 1
个点),有m
回,因此最多可以把n2n2n^2个点放入到小根堆中,因此每一次更新小根堆排序的情况是O(log(n2))O(log(n2))O(log(n^2)),一共最多m
次更新,因此总的时间复杂度上限是O(mlog((n2)))=O(2mlogn)=O(mlogn)O(mlog((n2)))=O(2mlogn)=O(mlogn)O(mlog((n^2)))=O(2mlogn)=O(mlogn)
疑问:为什么会存在距离已经确定了点在堆中?
因为可能上次新加入集合s的元素更新了a的距离值,但是距离值很大,直到a的距离值确定了才pop出来。
2.2边权值存在负数的情况
2.2.1 Bellman-ford算法
算法思想:如果图中存在n个点,那么经过n-1次循环,每轮循环时把每条边都进行松弛操作,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
松弛操作:
for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back[a] + w)
注意:back[] 数组是上一次迭代后 dist[] 数组的备份,由于是每个点同时向外出发,因此需要对 dist[] 数组进行备份,若不进行备份会因此发生串联效应,影响到下一个点。
在下面代码中,是否能到达n号点的判断中需要进行if(dist[n] > INF/2)
判断,而并非是if(dist[n] == INF)
判断,原因是INF
是一个确定的值,并非真正的无穷大,会随着其他数值而受到影响,dist[n]
大于某个与INF
相同数量级的数即可。
bellman - ford算法擅长解决有边数限制的最短路问题。
//本代码是解决有边数限制的最短路径问题的代码
#include
using namespace std;
const int N = 10010;
int n,m,k;
int dist[510],backup[510];
struct{
int a,b,w;
}edges[N];//a->b有一条边,权重为w
int bellman\_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i//最多k条边,总共最对经过k条边
memcpy(backup,dist,sizeof dist);
for(int j=0;j//对所有的m条边执行松弛操作
int a=edges[j].a,b=edges[j].b,w=edges[j].w;
if(backup[a]+wif(dist[n]>0x3f3f3f3f/2) return -0x3f3f3f3f;
else return dist[n];
}
int main(){
cin>>n>>m>>k;
int a,b,w;
for(int i=0;i>a>>b>>w;
edges[i]={a,b,w};
}
int ans=bellman\_ford();
if(ans==-0x3f3f3f3f){
cout<<"impossible"<else{
cout<return 0;
}
算法分析:
时间复杂度:O(nm)O(nm)O(nm),其中n为点数,m为边数
2.2.2 SPFA算法
算法思想:优化了Bellman-ford算法。在Bellman-ford算法中,dist[b] = min(dist[b],back[a] + w)
,如果a的距离没有更新,那么我的循环其实做了很多没用的操作。所以我们希望当a的距离更新时 ,再去用a更新其他结点的距离值。算法思想类似于Dijstra算法。
#include
using namespace std;
const int N = 1e5+10;
int e[N],w[N],h[N],ne[N],idx;
int n,m;
int st[N];//记录结点是否在队列中,即是否发生更新
int dist[N];
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
queue<int> q;
q.push(1);
while(!q.empty()){
int 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]){//结点发生距离更新,所以可以用该结点去更新其他结点
q.push(j);
st[j]=true;
}
}
}
}
if(dist[n]==0x3f3f3f3f) return -0x3f3f3f3f;
return dist[n];
}
int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
int a,b,c;
while(m--){
cin>>a>>b>>c;
add(a,b,c);
}
int ans=spfa();
if(ans==-0x3f3f3f3f) cout<<"impossible"<else cout<return 0;
}
算法分析:
Bellman_ford算法里最后return -1
的判断条件写的是dist[n]>0x3f3f3f3f/2;
而spfa算法写的是dist[n]==0x3f3f3f3f;
其原因在于Bellman_ford算法会遍历所有的边,因此不管是不是和源点连通的边它都会得到更新;但是SPFA算法不一样,它相当于采用了BFS,因此遍历到的结点都是与源点连通的,因此如果你要求的n和源点不连通,它不会得到更新,还是保持的0x3f3f3f3f。
Bellman_ford算法可以存在负权回路,是因为其循环的次数是有限制的因此最终不会发生死循环;但是SPFA算法不可以,由于用了队列来存储,只要发生了更新就会不断的入队,因此假如有负权回路请你不要用SPFA否则会死循环。
由于SPFA算法是由Bellman_ford算法优化而来,在最坏的情况下时间复杂度和它一样即时间复杂度为 O(nm)O(nm)O(nm) ,假如题目时间允许可以直接用SPFA算法去解Dijkstra算法的题目。
求负环一般使用SPFA算法,方法是用一个cnt数组记录每个点到源点的边数,一个点被更新一次就+1,一旦有点的边数达到了n那就证明存在了负环。
3.多源汇最短路径问题
Floyd算法
算法思想:三重循环,动态规划思想。dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
#include
using namespace std;
const int N = 510,INF=1e9;
int g[N][N];//g[i][j]记录i->j的最短路径
int n,m,Q;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
int main(){
cin>>n>>m>>Q;
for(int i=1;i<=n;i++){//初始化数组
for(int j=1;j<=n;j++){
if(i==j) g[i][j]=0;
else g[i][j]=INF;
}
}
while(m--){//输入m条边
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
floyd();
while(Q--){//Q次查询
int a,b;
cin>>a>>b;
if(g[a][b]>INF/2) cout<<"impossible"<else cout<return 0;
}
算法分析:三重循环,floyd算法时间复杂度为O(n)O(n)O(n)
-
- 1.图的最短路径问题分类
- 2.单源最短路问题
- 2.1边权值都是正数情况
- 2.1.1 朴素Dijstra算法
- 2.1.2 堆优化的Dijstra算法
- 2.2边权值存在负数的情况
- 2.2.1 Bellman-ford算法
- 2.2.2 SPFA算法
- 3.多源汇最短路径问题
- Floyd算法
__EOF__
Guagua - 本文链接: https://blog.csdn.net/xiaodaiguagua/p/16364893.html
转载请注明:xuhss » 图的最短路径问题 详细分解版