图的应用【最短路径】 —— Bellman-Ford 算法

如果遇到负权边，则在没有负环（回路的权值之和为负）存在时，可以采用Bellman-Ford算法求解最短路径。

Bellman-Ford算法用于求解单源最短路径问题，由理查德•贝尔曼和莱斯特•福特提出。该算法的优点是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但是，对该算法可以进行若干种优化，以提高效率。

Bellman-Ford算法与Dijkstra算法类似，都以松弛操作为基础。Dijkstra算法以贪心法选取未被处理的具有最小权值的节点，然后对其出边进行松弛操作；而Bellman-Ford算法对所有边都进行松弛操作，共n -1次。因为负环可以无限制地减少最短路径长度，所以如果发现第n 次操作仍可松弛，则一定存在负环。Bellman-Ford算法的最长运行时间为O (nm )，其中n 和m 分别是节点数和边数。

【算法步骤】

1 数据结构。因为需要利用边进行松弛，因此采用边集数组存储。每条边都有三个域：两个端点a 、b 和边权w 。

2 松弛操作。对所有的边j (a ,b ,w )，如果dis[e [j ].b]>dis[e [j ].a ]+e [j ].w ，则松弛，令dis[e [j ].b ]=dis[e [j].a ]+e [j ].w 。其中，dis[v ]表示从源点到节点v 的最短路径长度。

3 重复松弛操作n -1次。

4 负环判定（简称“判负环”）。再执行一次松弛操作，如果仍然可以松弛，则说明有负环。

【算法实现】

bool bellman_ford(int u){ //求从源点u 到其他节点的最短路径长度，并判断是否有负环
	memset(dis , 0x3f , sizeof(dis));
	dis[u] = 0;
	for(int i = 1; i < n ; i++){ //执行n - 1 次
		bool flag = 0;
		for(int j = 0 ; j < m ; j ++){ //边数m 或 cnt
			if(dis[e[j].b] > dis[e[j].a] + e[j].w){
				dis[e[j].b] = dis[e[j].a] + e[j].w;
				flag = true;
			}
		}
		if(!flag){
			return true;
		}
	}
	return false;
}

【算法优化】

1 提前退出循环。在实际操作中，Bellman-Ford算法经常会在未达到n -1次时就求解完毕，可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环。通过上段代码中的if(!flag)就可以提前退出循环。

2 队列优化。松弛操作必定只会发生在最短路径松弛过的前驱节点上，用一个队列记录松弛过的节点，可以避免冗余计算。这就是队列优化的Bellman-Ford算法，又被称为SPFA算法。