Bellman-Ford(BF)和Floyd算法

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

Floyd算法就比较暴力了，算法思想是三重循环，直接枚举所有的顶点，再两次for循环枚举所有点，验证以第一个点为中转点的两个点是否路径更短，具体就不实现了

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

但是BF算法完全不同，最外层的n-1次循环是为了保证成功构建n-1条路径，V个结点正好V-1个路径，如果转化成树则深度最多是V，但是在函数开始前根节点已经被访问了，所以最多只需要访问V-1次，其实不一定需要n-1次执行，可以适当剪枝，比如在n次循环中if(d[u]+length[u->v]<d[v)均为假，即没有可以松弛的边了，那就可以提前结束函数。内层的两次for循环的思想和dj差不多。

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->v];

			}

		}

	}

	for(each dege u->v){

		if(d[u]+length[u->v]<d[v])

		return false;

	}

	return true;

}

巴特西

Bellman-Ford(BF)和Floyd算法

最新文章

热门文章