Bellman算法的本质思想是什么?

发布网友发布时间：2022-05-25 15:02

共1个回答

热心网友时间：2023-11-07 00:17

你是说bellman ford最短路么;
如果是的话，对比Dijkstra，Dijkstra主要是贪心，Bellman ford主要是松弛。Bellman ford进一步的Floyd多源最短路就是DP了。但是非要说Bellman ford是啥本质思想，这还真不好归类。为了进一步理解Bellman ford，看看SPFA吧，SPFA算是拿出来Bellman ford有用的部分做的优化(虽然时间复杂度不稳定)。
总体来说，这货算是每次更新到确保当前迭代次数的边数是最优的。最后的最短路，中间路径最多间隔n-1条边。第一次更新，就确保如果这个点最终最短路和原点之间只有一条边，那就已经更新了。第二次更新是在第一次的基础上，保证最短路长度为2的所有点都更新了。直到最后n-1，就可以全部更新了