网上找的一些图论bellman

1、Bellman-Ford 算法及其优Bellman-Ford 算法与另一个非常著名的 Dijkstra 算法一样，用于求解单源点最短路径问题。Bellman-ford 算法除了可求解边权均非以解决存在负权（意义是什么，好好思考），而 Dijkstra 算法只能处理负，因此 Bellman-Ford 算法的适用面要广泛一些。是，原始的 Bellman-Ford 算法时间复杂度为 O（VE）,比 Dijkstra 法导论也只介绍了基本Bellman-Ford 算法及其优Bellman-Ford 算法与另一个非常著名的 Dijkstra 算法一样，用于求解单源点最短路径问题。Bellman-ford

2、 算法除了可求解边权均非以解决存在负权（意义是什么，好好思考），而 Dijkstra 算法只能处理负，因此 Bellman-Ford 算法的适用面要广泛一些。是，原始的 Bellman-Ford 算法时间复杂度为 O（VE）,比 Dijkstra 法导论也只介绍了基本的 Bellman-Ford 算法，在国内常见的基本信息学奥中也均未提及，因此该算法的知名度与被掌握度都不如 算法。事实上，有多种形式的 Bellman-Ford 算法，例如近一两年被热捧的 SPFA（Shortest-Faster Algoithm 更快的最短路径算法）算法的时间效率甚至由于 Dijkstra 算法，因此有关 B

3、ellman-Ford 算法的诸多问题常常困扰奥赛选手。如：该算法值得掌握么？怎样用编程语言具体实现？有哪些优化？与 SPFA 本文试图对 Bellman-算法做一个比较全面的介绍。给出几种实现程序，从理论和实测两方面分析他们的时间复杂度，供大家在备战省选和后noi 时参考Bellman-Ford 算法Bellman-Ford 算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）G=（V,E），其源点为 s权函数w集E 。对图 G 运行 Bellman-Ford 算法的结果是一个布尔值，表明图中是否存在着一个从源点 s 可达的负权回路。若不存这样的回路，算法

4、将给出从源点s G 的任意顶点v 的最短路径dvBellman-Ford 算法流程分为三个阶段：初始化：将除源点外的所有顶点的最短距离估计值dv ds 迭代求解：反复对边集 E 中的每条边进行松弛操作，使得顶点集 V 中的每个顶点 v 的最短距离估计值逐步 近其最短距离；（运行|v|-次检验负权回路：判断边集 E 中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回 false回 true，并且从源点可达的顶点 v 的最短距离保存在 dv算法描述如下Bellman-Ford(G,w,s) /G ，边集数w ，s 为源1foreachvertexv V（G）dv 2ds /134fo

5、ri=1to|v|-1/2 for each edge（u,v） E(G) do /边集数组要用到，穷举每条边5If4fori=1to|v|-1/2 for each edge（u,v） E(G) do /边集数组要用到，穷举每条边5Ifdvdu+w(u,v)/67/松弛操作 2阶段结foreachedge（u,v）E(G)8 9ExitExit首，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-条边s 可达的所有顶点如果 一个以 s 为根的最短路径树。Bellman-Ford 算法的迭代松弛操作，际上就是按顶点距离 s 在对每条边进行 1 遍松弛的时候，生成

6、了从 s 出发，层次至多为 1 的那些树枝。也就是说，找到了与 s 至多有 1 对每条边进行第 2 2 层次的树枝，就是说找到了经过 2 条边相连的那些顶点的最短路径|v|-条边，所以，只需要循环|v|-1 次（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行如果没有负权回路由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1 遍松弛操作后所有从 s 可达的顶点必将求出最短距离。如仍保持 +sv如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权的顶点不会收敛例如对于上图，边上方框中的数字代表权值，顶点 A,B,C 之间存在负权回路。S 是

7、源点，顶点中数字表示运行 Bellman-Ford 算法后各点的最此时 da的值为 1，大于 dc+w(c,a)的值-2，由此 da可以松弛为-2，然后 db又可以松弛为-5,dc又可以松弛为-7.下一个周期，da不会终止。因此，在迭代求解最短路径阶段结束后，可以通过检验边集 E 此时 da的值为 1，大于 dc+w(c,a)的值-2，由此 da可以松弛为-2，然后 db又可以松弛为-5,dc又可以松弛为-7.下一个周期，da不会终止。因此，在迭代求解最短路径阶段结束后，可以通过检验边集 E 的每条边(u,v)是否满足关系可以更新为更小的值，这个过du+ w(u,v) 来判断是否存在负权回路】61112223445125634645664-56-programw:array1.maxn,1.maxnofpre:array1.maxnvis:array1.maxn;procedureforu:=1to nforv:=1tonfori:=1to mw:array1.maxn,1.maxnofpre:array1.maxnvis:array1.maxn;procedureforu:=1to nforv:=1tonfori:=1to mprocedure;fori:=1tonfori:=1ton forj: