最短路径算法（Dijkstra、Bellman-Ford、SPFA、Floyd）

《算法笔记》笔记

解决最短路径问题的常用算法有Dijkstra、Bellman-Ford、SPFA、Floyd算法。

1、Dijkstra

（1） 解决单源最短路问题。即给定图G和起点s，通过算法得到S到达其他每个顶点的最短距离。只能应对所有边权都是非负数的情况，

Dijkstra(G,d[],s){
	fill(d,d+N,INF);
	d[s] = 0;
	for(循环n次）{
		u = 使d[u]最小的还未被访问的顶点的编号；
		记u已被访问；
		for(从u出发能到达的所有顶点v）{
			if(v未被访问&&以u为中介点使s到顶点v的最短距离d[v]更优）{
				优化d[v]
			}
		}
	}
}
           

（2） 时间复杂度：

• 使用邻接矩阵：外层循环O(V),内层循环（寻找最小的d[u]需要O(V)，枚举v需要O(V)），总复杂度为O(V*(V+V)) = O（V2）
• 使用邻接表：外层循环O(V），内层循环（寻找最小的d[u]需要O(V)、枚举v需要O（adj[u].size））产生，对整个程序来说枚举v的次数总共为O（ ∑ u = 0 u = n − 1 a d j [ u ] . s i z e \sum_{u=0}^{u=n-1}{adj[u].size} ∑u=0u=n−1​adj[u].size）=O(E),因此总的时间复杂度为O(V2+E）
• 使用堆优化。由于寻找最小d[u]的过程不必达到O(V）的复杂度，使用STL中的优先队列priority_queue，这样使用邻接表实现Dijkstra的时间复杂度可以降低到O(VlogV+E)

2、Bellman-Ford

（1）解决单源最短路径问题。可以处理有负权边的情况。

如果图中有负环，且从源点可以到达，负环的存在可以使最短路径更短，因此负环会影响最短路径的求解。但如果图中的负环无法从源点出发可达，则最短路径的求解不会受到影响。

for(i=0,i<n-1;i++){
	for(each edge u->v){
		if(d[u]+length[u->v]<d[v]){
			d[v] = d[u]+length[u->v];
		}
	}
}
/*如果图中没有从源点可达的负环，那么经过上述循环后数组d中的所有值应该达到最优
再对边进行一轮操作，如果仍然有从某条边u->v仍然满足d[u]+length[u->v]<d[v]，那么说明图中
存在从源点可达的负环，返回false；否则，说明数组d中的所有值都已经达到最优，返回true
*/
for(each edge u->v){
	if(d[u]+length[u->v]<d[v]){
		return false;
	}
	return true;
}
           

（2）时间复杂度

• 邻接表：O(VE）
• 邻接矩阵：O（V3）

3、SPLA

（1）虽然Bellman-Ford算法思路简洁，但是O(VE）的时间复杂度很高，在很多情况下表现不佳。Bellman-Ford算法的每轮操作都需要操作所有边，显然这其中会有大量无意义的操作，严重影响算法性能。只有当某个顶点u的d[u]值改变时，从它出发的边的邻接点v的d[v]才有可能被改变。 因此提出SPLA算法。

queue<int> Q;
源节点s入队；
while(队列非空）{
	取出队首元素u；
	for(u的所有邻接边u->v）{
		if(d[u]+dis<d[v]){
			d[v] = d[u]+dis;
			if(v当前不在队列){
				v入队;
				if(v入队次数大于n-1）{
					说明有可达负环，return;
				}
			}
		}
	}
}
           

（2） 时间复杂度

O（kE）,k是一个常数，很多情况呢下k不超过2,因此SPLA算法异常高效，经常性地优于Dijkstra算法。但是如果图中有从源点可达的负环，SPFA算法的时间复杂度为退化成O(VE)。

4、Floyd

（1）解决全源最短路问题，即给定的图G(V,E），求任意两点u,v之间的最短路径长度。

算法思想：如果存在顶点k，使得以k作为中介点时顶点i和顶点j的当前最短距离缩短，则使用顶点k作为顶点i和顶点j的中介点。即当dis[i][k]+dis[k][j]<dis[i][j]时，令dis[i][j] = dis[i][k]+dis[k][j]。

伪代码：
枚举顶点k∈[1,n]
	以顶点k作为中介点，枚举所有顶点对i和j（i∈[1,n],j∈[1,n]）
		如果dis[i][k]+dis[k][j]<dis[i][j]成立
			赋值dis[i][j] = dis[i][k]+dis[k][j]
           

注意：不能将最外层的k循环放到内层

void Floyd(){
	for(int k = 0;k<n;k++){
		for(int i = 0;i<n;i++){
			for(int j = 0;j<n;j++){
				if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){
					dis[i][j] = dis[i][k]+dis[k][j];
				}
			}
		}
	}
}
           

（2）时间复杂度为O(n3），由于n3的复杂度，决定了顶点数n限制在200以内，因此使用邻接矩阵来实现Floyd算法比较合适。