Bellman-Ford(BF)算法

以下只是本人的笔记，想法我自己都怀疑，内容不作为参考，

Dijkstra算法可以很好的解决无负权图的最短路径问题，但是如果出现负值权值就会失效。此时就需要BF算法，BF和dj算法都能解决单源最短路径问题，但是算法思想是完全不同的，dj是选取到起点路径最短的点，然后以该点为中心更新相关联的路径长，最外层的n次循环保证的是n个点均能被访问（见上篇博客）

但是BF算法完全不同，最外层的n-1次循环是为了保证成功构建n-1条路径，其实不一定需要n-1次执行，可以适当剪枝，内层的两次for循环是遍历每个点的所有边中的权值最小的边（我总觉得不大对）

bool Bellman(int s){
	for(int 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->];
			}
		}
	}
	for(each dege u->v){
		if(d[u]+length[u->v]<d[v])
		return false;
	}
	return true;
} 

　　在使用邻接矩阵时时间复杂度是v3，但在使用邻接链表时时间复杂度是VE，有一些减少时间复杂度的方法，比如

Bellman-Ford(BF)算法

原文：https://www.cnblogs.com/tao7/p/10244896.html