关于最短路的四种算法
关于最短路的四种算法
1.floyd
核心代码只有三个for循环：
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(map1[i][j]>map1[i][k]+map1[k][j])
map1[i][j]=map1[i][k]+map1[k][j];
}
}
} 这种算法可以找多源最短路，想知道a点到b点最短路，只能加入中间点来缩短路径，比如a到b 加入中间点k a到k到b
那么我们可以这样判断，要知道i到j的最短路，我们只要判断e[i][j]是否大于e[i][1]+e[1][j]即可，而中间值1则要用for循环从1到n遍历一个遍，就是查找所有中间值
//floyd
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int main()
{
int n,m,a,b,c;
int map1[100][100];
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1;j<=n;j++)
if(i==j) map1[i][j]=0;
else map1[i][j]=inf;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
map1[a][b]=c;
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
if(map1[i][j]>map1[i][k]+map1[k][j])
map1[i][j]=map1[i][k]+map1[k][j];
}
for(int i=1; i<=n; i++)
{
for(int j=1;j<=n;j++)
printf("%d ",map1[i][j]);
printf("\n");
}
return 0；
}2.dijkstra
这个算法只能计算单元最短路，而且不能计算负权值，这个算法是贪心的思想， dis数组用来储存起始点到其他点的最短路，但开始时却是存的起始点到其他点的初始路程。通过n-1遍的遍历找最短。 比如1到3的最短路就是比较dis[3]与dis[2]+e[2][3]，如果大于的话就更新dis[3]位dis[2]+e[2][3]，这个专业术语叫松弛，这种算法的核心思想就是通过边来松弛一号顶点到其他定点的路程，这也就能解释为什么要遍历n-1遍了。 book数组用来标记，被标记的是已经找过的最短路，没被标记的没有被找过的最短路，当全部找过以后算法结束，也就是说dis数组中的数是起始点到其他所有点的最短路 .
举个例题：poj1724，不仅使用了dijkstra，还使用了优先队列进行优化。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define mem(x) memset(x,0,sizeof(x))
#define LL long long
int n,k,r,cnt=0;
int head[10005],dis[10005][10005];
struct star
{
int next,v,dis,cost;
}g[10005];//使用链式前向星来储存边。
struct node
{
int num,dis,cost;
bool friend operator < (node a,node b){
return a.dis>b.dis;
}
};
void add_edge(int u,int v,int d,int c){
cnt++;//!!!
g[cnt].next=head[u];//!!!
g[cnt].v=v;
g[cnt].dis=d;
g[cnt].cost=c;
head[u]=cnt;////第一条边为当前边
}
void dijkstra(){
for (int i = 1; i <= n ; ++i)
{
for (int j = 0; j <= k; ++j)
{
dis[i][j]=inf;//对于i点，从1到i，花费j元的最短距离
}
}
dis[1][0]=0;
priority_queue<node >q;
node now,to;
now.num=1;
now.dis=0;
now.cost=0;
q.push(now);
while(!q.empty()){
now=q.top();
q.pop();
if(now.num==n){
cout<<now.dis<<endl;
return ;
}
for(int i=head[now.num];i!=-1;i=g[i].next){
int cost=now.cost+g[i].cost;
if(cost>k) continue;
if(dis[g[i].v][cost]>now.dis+g[i].dis){
dis[g[i].v][cost]=now.dis+g[i].dis;
to.num=g[i].v;
to.cost=cost;
to.dis=dis[g[i].v][cost];
q.push(to);
}
}
}
cout<<"-1";
}
int main(int argc, char const *argv[])
{
cin>>k>>n>>r;
memset(head,-1,sizeof(head));
for (int i = 0; i < r; ++i)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
add_edge(a,b,c,d);
}
dijkstra();
return 0;
}3.Bellman_Ford
先介绍一下负权回路，如果是单向图，那么所有权值之和为负数，这是负权回路。
如果是无向图只要有一个负权值，就不会存在最短路，跟负权回路一个意思。 这个算法一般用于有负权值的最短路，但时间复杂度也不高。 有负权值的最短路 有了负权值dijkstra这种算法就不能用了，为什么呢？
因为dijkstra算法是贪心的思想，每次松弛的的前提是用来松弛这条边的最短路肯定是最短的。然而当有负权值的时候这个前提不能得到保证，所以dijkstra这种算法不能成立。
这里给出一个博客，这个讲很清晰。：https://blog.csdn.net/baidu_31818237/article/details/50611592
Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为, Distant[s]为0；
以下操作循环执行至多n-1次，n为顶点数：
对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出 单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).
Bellman－Ford算法可以大致分为三个部分
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
d（v） > d (u) + w(u,v)
则返回false，表示途中存在从源点可达的权为负的回路。
之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。
至于为什么是n-1次呢。dijkstra算法n-1次遍历是因为有n-1个点需要遍历，这个也是因为最短路是一个不包含回路的路径，无论正负权回路都不能有，那么去掉回路，n个点任意两点之间就最多有n-1条边。但是程序可能在不到n-1次循环就已经找到了所有最短路，说明这个是最坏情况下是n-1次遍历。
在本算法中dis[]同样是存起始点到各个顶点的最短路，这个与dijkstra不同的是，dijs每次找到最近的点进行松弛操作，而这个bellman则是只要路程更短我就松弛。也是因为这样才能用来解决负权值问题。
那么怎么来看有负权值回路呢，如果有负权值回路，那最短路就不会存在，因为最短路会越来与小。那么在n-1轮松弛后，要是还能松弛就代表有负权值回路。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define mem(x) memset(x,0,sizeof(x))
#define maxn 100010
int dis[maxn],u[maxn],v[maxn],w[maxn];
int main(int argc, char const *argv[])
{
int n,flag1,flag2,m;
while(~scanf("%d%d",&n,&m)){
for (int i = 1; i <= m; ++i)
{
cin>>u[i]>>v[i]>>w[i];
}
for(int i=1;i<=n;i++){
dis[i]=inf;
}
dis[1]=0;
for(int t=1;t<=n-1;t++){
flag1=0;
for(int i=1;i<=m;i++){
if(dis[v[i]]>dis[u[i]]+w[i]){
dis[v[i]]=dis[u[i]]+w[i];
flag1=1;
}
}
if(flag1==0)
break;
}
flag2=0;
for(int i=1; i<=m; i++)
if(dis[v[i]]>dis[u[i]]+w[i])
flag2=1;
if(flag2==1)
printf("有负权回路\n");
else
{
for(int i=1; i<=n; i++)
cout<<dis[i]<<" ";
}
cout<<endl;
}
return 0;
}4.SPFA（队列优化的bellman）
求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于1994年发表的。从名字上就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra算法等便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。
SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。 ——摘自《百度百科》
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define mem(x) memset(x,0,sizeof(x))
#define maxn 10010
int n,m,cnt=0;
int head[maxn],dis[maxn],inque[maxn];
struct star
{
int to,next,w;
}g[maxn];
void add_edge(int u,int v,int w){ //存图 ，x到y有一条权重为c的边
g[++cnt].next=head[u];
g[cnt].to=v;
g[cnt].w=w;
head[u]=cnt;
}
void SPFA(){
queue<int >q;
q.push(1);
dis[1]=0;
inque[1]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inque[u]=0;
for(int p=head[u];p!=0;p=g[p].next){
int v=g[p].to;
if(dis[v]>dis[u]+g[p].w){
dis[v]=dis[u]+g[p].w;
if(inque[v]==0){
q.push(v);
inque[v]=1;
}
}
}
}
}
int main(int argc, char const *argv[])
{
cin>>n>>m;
mem(head);mem(dis);mem(inque);
for (int i = 0; i < n; ++i)
{
dis[i]=inf;//初始化为inf
}
dis[1]=0;
for (int i = 0; i < m; ++i)
{
int a,b,c;
cin>>a>>b>>c;
add_edge(a,b,c);
add_edge(b,a,c);
}
SPFA();
cout<<dis[n]<<endl;
return 0;
}
