Can you summarize the following document?
        
  贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而贝尔曼-福特算法简单地对所有边进行松弛操作,共formula_3次,其中formula_4是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。  贝尔曼-福特算法的最多运行formula_5(大O符号)次,formula_6和formula_7分别是节点和边的数量)。

  procedure BellmanFord("list" vertices, "list" edges, "vertex" source)

  

  每次循环操作实际上是对相邻节点的访问,第formula_8次循环操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过formula_3条边,所以可知贝尔曼-福特算法所得为最短路径。

  与迪科斯彻算法不同的是,迪科斯彻算法的基本操作“拓展”是在深度上寻路,而“松弛”操作则是在广度上寻路,这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

  因为负权环可以无限制的降低总花费,所以如果发现第formula_8次操作仍可降低花销,就一定存在负权环。

  当使用这个算法寻找最短路径时,有负回路会使算法找不到正确的答案。但是,由于在找到负回路后会中止算法,所以可以被用来寻找目标,例如在网络流分析中的消圈算法(Cycle Cancellation Algorithms)

  

  在实际操作中,贝尔曼-福特算法经常会在未达到formula_11次前就出解,formula_11其实是最大值。于是可以在循环中设置判定,在某次循环不再进行松弛时,直接退出循环,进行负权环判定。

  西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上,用一个队列记录松弛过的节点,可以避免了冗余计算。原文中提出该算法的复杂度为formula_13,formula_14是个比较小的系数,但该结论被证明不适于于所有情况。  Pascal语言示例  C++语言示例 int SPFA(int s) {

  例:  运行如表: formula_16
贝尔曼-福特算法(英语:Bellman–Ford algorithm),求解单源最短路径问题的一种算法,由理乍得·贝尔曼(Richard Bellman) 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行formula_1次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达formula_2。但算法可以进行若干种优化,提高了效率。