欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

最短路径问题：Dijkstra算法、Floyd算法、Bellman-Ford算法和SPFA算法

程序员文章站 2022-04-05 22:51:41
...

最短路径问题就是在网络中，让我们求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径，对于不同种类的图和我们我们分为以下几种情况：
（1）单源最短路径：
从固定源点出发，求其到所有其他顶点的最短路径。
（2）多源最短路径：
任意两顶点间的最短路径。
（3）无权图的最短路径：
就是经过边个数最少（也是经过顶点数最少的）的路径，边的个数（顶点数-1）即为最短路径长度。
（4）有权图的最短路径：
那就不一定是经过顶点/边最少的了，而且还有可能权值小于0，所以这个是比较复杂的。
前两种情况和后两种情况各取一种可以排列为4种情况，下面我们来看对应的解决方法。

1.无权图的单源最短路径：

也就是找经过边个数最少（也是经过顶点数最少的）的路径，边的个数（顶点数-1）即为最短路径长度（因为边的权值均为1）。就是在BFS的基础上加上记录长度的变量。
我们假设s为源点,w为当前访问的顶点：

vector<int> G[N];//用邻接表表示图
int dist[N]={-1};//dist[w]的值记录s到w的最短路径，初始化为-1表示还未被访问
dist[s]=0;//自己到自己的距离是0
int path[N]={-1};//path[w]的值记录w到s必经之路的上一个顶点，初始化为-1
void NoWeight(int s)
{
	queue<int> Q;
	Q.push(s);
	while(!Q.empty()){
		int v=Q.front();
		Q.pop();
		for(int w=0;w<G[v].size();w++){//遍历v的邻接点
			if(dist[w]==-1){//w还没被访问过
				dist[w]=dist[v]+1;
				path[w]=v;//下面会说path的作用
				Q.push(w);				
			}
		}
	}
}

这样我们就可以得到所有顶点到s的最短路径了（全部存在dist数组中），那么path数组有什么作用呢？想一下，我们在求完所有顶点到s的最短路径后，如果让我们输出顶点w到s的最短路径上的所有顶点，因为path[w]的值记录w到s必经之路的上一个顶点，我们可以用path[w]得到他到s的最短路径上的上一个顶点，再看上一个顶点的path，一直到path值等于s，这样我们就能得到顶点w到s的最短路径上的所有顶点。（后面的也一样）
时间复杂度：while循环遍历了所有顶点（Nv），for循环相当于遍历了所有的边（Ne），故时间复杂度为O（Nv+Ne）。

2.有权图的单源最短路径：Dijkstra算法

因为边有了权值，所以不能用边的个数来表示单源最短路径了，甚至还因为有可能权值为负造成负值圈（如果有一个封闭的子图其中有权值为负的边，那么会在这个圈里面无限循环，因为越加越小嘛，形成了负值圈），在Dijkstra算法中我们只考虑权值非负的情况。
最短路径问题：Dijkstra算法、Floyd算法、Bellman-Ford算法和SPFA算法
首先注意我们是要得到所有顶点到s的最短路径，不要总想着一个，所以集合S中存的是所有能到s的顶点！！！我们来分析一下：在第三点的第一项中真正的最短路必须只经过S集合中的顶点，因为S集合中每次存入一个顶点v都是进行第三项，也就是遍历v的邻接点，如果v在s和某个邻接点w之间并且s->v->w的路径长度小于原来收录在S集合中s到w的路径长度（dist[w]），就会更新dist[w]和path[w]的值。看代码：
说这么麻烦，其实还是改造了BFS，只不过跟无权图的做法相比Dijkstra算法更新的内容是未被收录的顶点中dist最小的顶点的邻接点的数据。

int G[N][N];//用二维数组的邻接矩阵表示图，且值均大于等于0
int dist[N]={-1};//dist[w]的值记录s到w的当前路径，是s的邻接点则初始化为G[s][W],不是则为-1
dist[s]=0;//自己到自己的距离是0
int path[N];//path[w]的值记录w到s必经之路的上一个顶点，是s的邻接点则初始化为s否则初始化为-1
bool collected[N];//看是否被收录进S
int FindMinDist()//寻找未被收录进S的dist值最小的顶点
{
	int MinV,V,MinDist=INFINITY;
	for(V=0;V<N;V++){
		if(collected[V]==false&&dist[V]<MinDist){/* 若V未被收录，且dist[V]更小 */
			MinDist=dist[V];
			MinV=V;
		}
	}
	if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在，返回错误标记，自己定义一个ERROR */
}
bool Dijkstra( int s )
{
    int V, W;
    /* 初始化：此处默认邻接矩阵中不存在的边用0表示 */
    for ( V=0; V<N; V++ ) {
        dist[V] = G[s][V];
        if ( dist[V]>0 )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    collected[s]=true;/* 先将起点收入集合 */
    while(1){
        V = FindMinDist();/* V = 未被收录顶点中dist最小者 */
        if(V==ERROR) break;//找不到更小的V了结束
        collecte[V]=true;//把V收录进S
        for(W=0;W<N;W++){//遍历所有顶点找V的邻接点
			if(collected[W]==false&&G[V][W]>0){
				if(dist[V]+G[V][W]<dist[W]){//更新W的数据
					dist[W]=dist[V]+G[V][W];
					path[W]=V;
				}
			}
		}
    }
    return true;
}

时间复杂度：
因为是要遍历所有顶点找到当前未被收录的最小dist的顶点，找到后还要遍历所有顶点找他的邻接点来更新邻接点的dist的数据，所以时间复杂度将达到O（Nv2+Ne），对于稠密图来说还是比较划算的。如果图比较稀疏，我们可以用最小堆来存dist值（这样每次找最小dist就是O(logNv)），用STL库中的优先队列priority_queue代替最小堆来存更方便：

priority_queue<int,vector<int>,greater<int> > dist;

然后我们就只找邻接点（相当于遍历所有的边O(Ne)），故对于稀疏图时间复杂度可以改进为O(Ne*logNv)。

3.多源最短路径：Floyd算法

既然我们已经解决了单源最短路径问题，那么我们完全可以让每个顶点都作为源点得到两两之间的最短路径，也就是多源最短路径。这样的时间复杂度就是Nv单源最短路径的时间复杂度=O（Nv^3+NvNe）
适用于稀疏图，我们还可以采用类似Dijkstra算法每次更新dist的方法来处理稠密图（用矩阵来表示），采取递推的方式，也就是依次遍历所有可能出现的两对相邻路径和一对包含这两对相邻路径的路径，看范围大的路径是否大于两对相邻路径，再决定是否更新：

int G[N][N];//用二维数组的邻接矩阵表示图，且值均大于等于0
int dist[N][N];//dist[v][w]的值记录v到w的当前最小路径
int path[N][N];
void Floyd()
{
	int i,j,k;
	/*初始化*/
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			dist[i][j]=G[i][j];
			path[i][j]=-1;
		}
	}
	/*更新dist和path*/
	for(k=0;k<N;k++){
		for(i=0;i<N;i++){
			for(j=0;j<N;j++){
				if(dist[i][j]>dist[i][k]+dist[k][j]){//i->k，k，k->j
					dist[i][j]=dist[i][k]+dist[k][j];
					if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                        return false; /* 不能正确解决，返回错误标记 */
					path[i][j]=k;
				}
			}
		}
	}
}

注意上面每一步更新的都是i->k，k，k->j三段路径组成的最小路径。

4.权值存在负数的情况：Bellman-Ford算法和SPFA算法

前面我们说到了权值为负造成负值圈（如果有一个封闭的子图其中有权值为负的边，那么会在这个圈里面无限循环，因为越加越小嘛，形成了负值圈）Bellman-Ford算法可以解决存在负值和负值圈的有权图的单源最短路径，我们可以在进行完Dijkstra算法后再对每条边进行判断，看源点是否能连通负值圈：

struct node{
	int v;//邻接点
	int weight;//边的权值
}
vector<node> G[N];//用邻接表表示便于找邻接点
int dist[N];
dist[s]=0;
bool Bellman(int s)
{
	int i,j,k;
	 /* 初始化：此处默认邻接矩阵中不存在的边用0表示 */
    for ( i=0; i<N; i++ ) {
        dist[i] = G[s][i];
    }
	//更新dist的数据
	for(i=0;i<N-1;i++){//进行N-1轮操作，因为最多有N-1层的图，对每一层进行判断
		for(j=0;j<N;j++){//对于每个顶点
			for(k=0;k<G[j].size();j++){//的所有边
				int v=G[j][k].v;
				int w=G[j][k].weight;
				if(dist[j]+w<dist[v])
					dist[v]=dist[j]+w;
			}
		}
	}
	//最后判断是否存在与源点相连的负值圈。
	for(j=0;j<N;j++){//对于每个顶点
		for(k=0;k<G[j].size();j++){//的所有边
			int v=G[j][k].v;
			int w=G[j][k].weight;
			if(dist[j]+w<dist[v])//还未达到最优
				return false;
		}
	}
	return true;
}

显然如果我们对所有的点所有的边都分层进行dist值的更新，那时间复杂度将是立方，对稠密图还行。因为只有一层中每个顶点最小的dist值变化，它邻接点（下一层的）dist值才会变化，所以我们可以用一个队列（来存dist变化的顶点，这样我们就只用处理会变化的顶点，而不用判断所有顶点），每次去除队首顶点，在它的邻接点进行dist值更新前的判断dist[j]+w<dist[v]时，看看是否成立（也就是邻接点的dist要变化），如果成立并且v不在队列中就把v加入到队列中，这样一直到队空，就说明没有源点可达负值圈，但如果v的入队次数大于n-1（说明已经对所有层进行了操作）则说明有负值圈。这种方法就是SPFA算法。大致形式如下：

struct node{
	int v;//邻接点
	int weight;//边的权值
}
vector<node> G[N];//用邻接表表示便于找邻接点
bool inq[N];//判断v是否在队列中
int num[N]={0};//判断v进入队列的次数
int dist[N];
bool SPFA(int s)
{
	//dist、inq初始化自己写
	queue<int> Q;
	Q.push(s);
	inq[s]=true;
	num[s]++;
	while(!Q.empty()){
		int v=Q.front();
		Q.pop();
		inq[v]=false;
		for(int w=0;w<G[v].size();w++){
			if(dist[v]+G[v][w].weight<dist[w]){
				dist[w]=dist[v]+G[v][w].weight;
				if(inq[w]==false) {
					Q.push(w);
					inq[w]=true;
					num[w]++;
					if(num[w]>N-1) return false;
				}
			}
		}
	}
	return false;
}
相关标签： c++的学习总结以及数据结构与算法

上一篇： 实训第六天

下一篇： 简单排序之选择排序

推荐阅读