2168048 2006-12-11 16:57:17 Accepted 2770 C++ 00:00.59 676K Crux.D     图论是一种美妙的东西。虽然不能化粪土为金钱，但是很多看上去不可能的任务可以用简单的转换完成。当然，其中的奥妙就在于「转换」二字。     因此，为了顺利完成从菜鸟成长为大菜鸟的计划，我决定学习进阶图论。 ---------------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) ---------------------------注意的分隔线------------------ 算法是不断更新的，即Distance(v) = Distance(u) + w(u,v) 不考虑先后情况。我一开始用了dp的方法，以为v和u要保存，结果wa了两次... 当更新完毕，Distance(v) <= Distance(u) + w(u,v);  这点非常重要，虽然目前看不出来......

评论