图论最短路径之Bellman-Ford算法代码模板及其优化

ゝ一纸荒年。 2023-02-28 12:56 2阅读 0赞

#### 一、对比Dijkstra算法 ####

**1、[Dijkstra算法][Dijkstra]的局限性**  
dijkstra算法适用的图**不能含有负权值**的边，若含负权值，可能会导致求得的答案错误。如下图：  
![举例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]  
以0为源点，首先确定到最近的2号点距离为5，然后确定到1号点的距离为7。但实际到2号点可经过1号点中转，经过负权值的边到2号点的距离为2 。  
所以当图中出现了负权值的边，就要用Bellman-Ford算法。

**2、Bellman-Ford算法的局限性**  
Bellman-Ford算法的图中不能有负权值回路（总权值和为负数的回路），如下图：![举例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 1]  
此图中0到1出现了总权值为-1的负权值回路，此时若从0点到1点再到0点再到1点如此无限循环会最短距离变到无限小，从而无法得到答案。

--------------------

#### 二、Bellman-Ford算法思想 ####

**算法基本思想：** 计算某一顶点到其他顶点的最短距离，①首先借助一个顶点中转，计算源点到其他顶点的最短距离，②然后借助两个顶点中转，③…直到借助n-1个顶点中转，得到的就是最短距离。  
\*\*算法关键原理：\*\*用一个dis数组重复覆盖，实现借助一个顶点、两个顶点、直到n-1个顶点，dis\[i\]是指源点到i顶点的最短距离。

**核心代码：** Bellman-Ford算法的核心代码只有四行

for(int i = 1;i < n;i++)
    	for(int j = 0;j < n;j++)
    		if(dis[j] > dis[u[j]]+w[j])
    			dis[j] = dis[u[j]]+w[j];

**代码模板：**

#include<iostream>
    using namespace std;
    const int N = 50,INF = 0x3f;
    
    int dis[N],u[N],v[N],w[N],n,m;
    
    void bellman(int start)
    { 
    	for(int i = 1;i <= n;i++)	//初始化dis数组
    		dis[i] = INF;
    	dis[start] = 0;			//出发的的距离确定为0
    
    	for(int i = 0;i < n-1;i++)	//最外层循环n-1轮
    		for(int j = 0;j < m;j++)	//直接循环m条边
    			if(dis[v[j]] > dis[u[j]] + w[j])	//对每条边进行松弛操作，判断经过该边中转是否距离更近，若更近，则更新dis数组
    				dis[v[j]] = dis[u[j]] + w[j];
    }
    
    int main()
    { 
    	cin >> n >> m;
    	for(int i = 0;i < m;i++)
    		cin >> u[i] >> v[i] >> w[i];	//输入边的信息，分别存第i条边的起点、终点、权值
    
    	bellman(1);
    
    	for(int i = 1;i <= n;i++)
    		cout << dis[i] << " ";
    
    	return 0;
    }

--------------------

#### 三、Bellman-Ford算法的分析 ####

**1、时间复杂度：** 显然，如此存边或用邻接表存边的时间复杂度是O(nm)，若用邻接矩阵存边的时间复杂度是O(n*3*)。

**2、检测是否存在负权回路：** 如前文所说，若在n-1轮松弛后，也就是完成bellma算法后，仍可对某条边松弛

if(dis[v[j]] > dis[u[j]] + w[j])
    	dis[v[j]] = dis[u[j]] + w[j];

就说明该回路中存在负权回路

**3、Bellman-Ford算法的优化：**  
①我们说，对边的松弛最多进行n-1轮，但若在这之前的某轮内没有对边进行松弛，说明所有松弛已经完成，就可以退出循环了。  
我们对上文的bellman算法进行优化

void bellman (int start)
    { 
    	for(int i = 1;i <= n;i++)
    		dis[i] = INF;
    	dis[start] = 0;
    	
    	int check = 1;
    	for(int i = 0;i < n-1;i++)
    	{ 
    		check = 1;	//check初始化为1
    		for(int j = 0;j < m;j++)
    		{ 
    			if(dis[v[j]] > dis[u[j]] + w[j])
    			{ 
    				dis[v[j]] = dis[u[j]] + w[j];
    				check = 0;	//若更新了某点的距离，check更新为0
    			}
    		}
    		if(check)	//若check为1，说明判断过每条边都没有变化，就结束算法，已达到最小距离
    			break;
    	}
    }

②队列优化  
只有当一条边松弛后，以该边的终点为起点的所有边会松弛，而其他边不会有该边，所以我们用一个队列（像bfs一样）将所有松弛的边的终点存下来，然后每次从队首拿出一个终点来对其的出边进行松弛。  
队列优化就是一个[SPFA算法][SPFA]，具体[可见此处。][SPFA]

[Dijkstra]: https://blog.csdn.net/qq_45735851/article/details/106564326
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: /images/20230209/b99d2a00934d479c8ce75f4233258823.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020072116392311.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[SPFA]: https://blog.csdn.net/qq_45735851/article/details/107517718