Bellman-Ford 算法

根据之前最短路径算法里提到的，我们只要放松所有边直到其全部失效就可以得到最短路径

注意：图中不能有负圈。否则当负圈中某个点经过这个负圈的所有边的松弛操作后，这个点的的d[i]就会减小，此时会发现它可以通过这个负圈的松弛操作不断使它自身不断变小。对于存在负圈的图，最短路无意义 

 由于是有关边的算法，并且我们不需要关注边之间的关系，只需要放松所有边即可

模板入下：

struct edge {int from, to, cost};edge es[MAX_E]; //边 int d[MAX_V]; int V, E;for (int i = 1; i <= V; i++) d[i] = INF; d[s] = 0; while (true) {bool update = false;for (int i = 1; i <= E; i++) {edge e = es[i];//d[e.from]=INF时距离为无穷大，没有意义 if (d[e.from]!=INF && d[e.to]>d[e.from]+e.cost]) {d[e.to] = d[e.from] + cost;update = true;}}if (!update) break; }

 

转载于:https://www.cnblogs.com/wizarderror/p/10902607.html

总结

以上是生活随笔为你收集整理的Bellman-Ford 算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。