最短路
下面依次来讲解.......
1:Flyod
弗洛伊德 (Floyd) 是解决最短路径的算法, 可以求出任意两点间的最短路径.
使用条件:
1: 可以出现负边权
2: 不是单源 (只有一个起始点) 算法
利与弊:
利: 跑一次即可求出任意两点最短路径, 且可以存在负边权
弊: 时间复杂度不是一般的高, O(n 的 3 方)
核心代码:
- for(int k=1;k<=n;k++)
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
if(k!=i && i!=j && k!=j && dis[i][k]+dis[k][j]<dis[i][j])
- dis[i][j]=dis[i][k]+dis[k][j];
- // 注意: dis[i][k]+dis[k][j]中的 i,k,j 的顺序不要写反了!
- 2:Dijkstra
迪杰斯特拉 (Dijkstra) 是处理最短路径的算法. 可求出一点到任意点的最短路径
条件:
1: 是单源算法
2: 不能存在有负边权
利与弊:
利: 时间复杂度较低, 为 O(n 的 2 方)
弊: 不能处理负边权, 且只能处理一点到任意点距离
核心代码:
- memset(dis,0x3f,sizeof(dis));
- dis[start]=0;
- int minn,k;
- for(int i=1;i<=n;i++)
- {
- minn=0x3f,k=0;
- for(int j=1;j<=n;j++)
- {
- if(!b[j] && dis[j]<minn)
- {
- minn=dis[j];
- k=j;
- }
- }
- if(k==0) break;
- b[k]=1;
- for(int j=head[k];j!=0;j=edge[j].next)
- {
- if(edge[j].w+dis[k]<dis[edge[j].to])
- dis[edge[j].to]=edge[j].w+dis[k];
- }
- }
- 3:SPFA
SPFA 算法是处理最短路径的一种算法, 它不能处理负环回路
条件:
1: 是单源算法
2: 不能处理负环
利与弊:
利: 时间复杂度低, 可以说是几种最短路中最优的算法
弊: 好像没有...
核心代码:
- memset(dis,0x3f,sizeof(dis));
- queue<int> zhou;
- zhou.push(1); dis[1]=0; b[1]=1;
- while(!zhou.empty())
- {
- int now=zhou.front(); zhou.pop(); b[now]=0;
- for(int i=head[now];i!=0;i=edge[i].next)
- {
- if(dis[now]+edge[i].dis<dis[edge[i].to])
- {
- dis[edge[i].to]=dis[now]+edge[i].dis;
- if(!b[edge[i].to])
- {
- b[edge[i].to]=1;
- zhou.push(edge[i].to);
- }
- }
- }
- }
当然了, 这里有几道题, 可以去洛谷看看, 并训练训练
- https://www.luogu.org/blog/BigYellowDog/p2384-zui-duan-lu (SPFA 模版题)
- https://www.luogu.org/blog/BigYellowDog/p2910-usaco08open-xun-bao-zhi-lu-clear-and-present-danger (Floyd 模版题)
- https://www.luogu.org/blog/BigYellowDog/p1346-dian-ju (最短路变式题)
最短路
来源: http://www.bubuko.com/infodetail-2579244.html