图论是一种美妙的东西。虽然不能化粪土为金钱，但是很多看上去不可能的任务可以用简单的转换完成。当然，其中的奥妙就在于「转换」二字。

    因此，为了顺利完成从菜鸟成长为大菜鸟的计划，我决定学习进阶图论。

---------------BVB养成计画·第一话   BellmanFord-------------------

    BellmanFord是一种计算最短路径的算法。虽然之前学过相当多的最短路径，如Dijkstra算法，Floyd算法，但他们是有适用范围的。即两算法下边的权值不能为负。因为考虑以下情况：

  出点 入点  权值

    1      2       -3

    2      3       -2

    3      1       2

    这样即构成了一条从1点到3点的负值回路-3 + -2 + 2 = -3，这样永远算不出1到3的最短路径了（因为可以无限循环-3 -6 -9....）。

    所以BF算法是专门提出来解决上述问题的－－计算每个点对源点s的最短路径。

    算法的伪代码如下

BF(G,w,s)

//   假设一张图G，从源点s出发，每条u至v的边权值为w(u,v)，共有n格点。

Determine Single Source(G,s);  set Distance(s) = 0;

for each vertex v in G other than s,
   set Distance(v) = infinity;   

//    首先把除了s点以外的距离置无限大

for i <- 1 to |V(G)| - 1 do   // 执行n－1次
   for each edge (u,v) in G do
      if Distance(v) > Distance(u) + w(u,v) then
         set Distance(v) = Distance(u) + w(u,v); 

//    对每条边，如果出点的距离>入点+边权值则更新

//  以下是检查，若还有更新则说明存在无限循环的负值回路
for each edge (u,r) in G do
   if Distance(r) > Distance(u) + w(u,r);
      return false;                    

return true;      

 //    完成，每个点r的最短路径为Distance(r)

---------------------------注意的分隔线------------------

1. 算法是不断更新的，即Distance(v) = Distance(u) + w(u,v) 不考虑先后情况。我一开始用了dp的方法，以为v和u要保存，结果wa了两次...
2. 当更新完毕，Distance(v) <= Distance(u) + w(u,v);  这点非常重要，虽然目前看不出来......

评论