bellmanford

贝尔曼-福特算法（Bellman-Ford Algorithm）是一种用于解决带权有向图中单源最短路径问题的算法。它是由Richard Bellman和Leon Ford在1958年独立提出的。该算法的主要思想是通过对图中的所有边进行V-1次松弛操作，来逐步更新从源节点到其他所有节点的最短路径。在每次松弛操作中，算法会检查当前边的前驱节点是否已经更新过，如果没有，则更新前驱节点并将边的权重累加到当前节点的距离上。通过V-1次松弛操作后，如果存在负权重环路，那么最短路径算法将无法得到正确的结果。因此，贝尔曼-福特算法还具有检测负权重环路的功能。