bellman-ford[bellmanford算法和floyd算法]
币安(Binance)最新可用网址（点击下图直达注册！）
最近有很多小伙伴咨询关于bellman-ford的问题，小编结合多年的经验整理出来一些bellmanford算法和floyd算法对应的资料，分享给大家。
Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权，在没有负权回路存在时（负权回路的含义是，回路的权值和为负。）即便有负权的边，也可以采用Bellman-Ford算法正确求出最短路径，。
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w是 边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。
简单来说就是从源点到一个点的最短路最极限的一种情况的路径需要经过全部的点，也就是需要松弛v-1次，这样，我们执行v-1次就可以保证所有的点都松弛到最佳的情况，如果执行了v-1次后还能继续松弛，那就说明图中有负权环，无解。
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
在对每条边进行第1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）
注意：上述只对正权图有效。如果存在负权不一定第i次就能确定最短路，且与边的顺序上述文章内容就是。
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v| 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
经过以上对bellman-ford的分享介绍，相信你对bellmanford算法和floyd算法有了大概的了解，想知道更多关于bellman-ford的知识，关注东方区块链网，我们将持续为您分享！