关于最短路的四种算法

关于最短路的四种算法

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;
}

 

喜欢()
评论 (0)
热门搜索
37 文章
3 评论
11 喜欢
Top