bellmanford

贝尔曼-福特算法（Bellman-Ford Algorithm）是一种用于解决带负权边的单源最短路径问题的动态规划算法。它是由Richard Bellman和Leon Ford在1958年独立提出的。该算法的主要思想是通过对图中的所有边进行V-1次松弛操作，来逐步减小从源点到其他所有顶点的最短路径估计值。在每次松弛操作中，算法会检查是否存在一条更短的路径，如果存在，则更新当前顶点的最短路径估计值。通过V-1次松弛操作后，算法可以确保找到从源点到所有其他顶点的最短路径。需要注意的是，贝尔曼-福特算法不能处理存在负权重环的图。