Bellman Ford - Bellman Ford算法
问题
设图中顶点可以到达任意其他顶点，用Bellman Ford算法求顶点到其他所有顶点的最短距离。
解法
设为两端点为顶点的边的距离，数组表示从顶点到的最短距离。
初始时，顶点到自己的距离为0（即），到其他顶点的距离为无穷大；
进行两层遍历，外层重复次数为点集的数量（外层重复次必然可以求出到所有其他顶点的最短距离），内层遍历边集中的所有边，设的两端点为。对顶点进行松弛操作：
若，则更新距离；
若，则更新距离；
顶点到任意其他顶点的最短距离为。若某个顶点的最短距离，则说明该图不存在最短路径。
该算法时间复杂度为。