最短路算法-Bellman-Ford_用循环法求最短路径的基本思想

一、基本思想 

        设共有N个节点，则进行N-1次循环，每一次循环中，针对每一个节点，计算其与起始点的最短距离并进行更新，并最终能够得到起始点到其余各点的最短路径。该算法与dijkstra算法相似，但不同之处在于，dijkstra算法每一次循环中更新与标号节点相连的未标号节点的最短距离，而bellman-ford算法则是在每一次循环中更新所有节点的最短距离，也正是因为这个差别，使得bellman-ford算法能够处理带负权弧的最短路问题并识别出是否存在负权回路。

        以上图为例，共有6个节点，因此需要进行5次循环。以数组dist表示起始点0到各节点的最短距离，初始时dist[0]=0，其余均为inf。

则循环过程如下：

第一次循环：dist=[0, 3, 1, 6, 7, 10]

第二次循环：dist=[0, 2, 1, 6, 6, 9]

第三次循环：dist=[0, 2, 1, 6, 6, 9]

第四次循环：dist=[0, 2, 1, 6, 6, 9]

第五次循环：dist=[0, 2, 1, 6, 6, 9]

        可以发现，其实第 i 次循环，就是找到了距离起始点 i 步以内的最短距离，也就是将每个节点作为距离起始点深度为 k (k < i) 的最短距离，而一个具有N个节点的图，最短路径的深度最大为N-1，因此最多需要N-1次循环可以找到最短路径。

        此外，我们还可以发现，在第3次循环之后，dist数组不再发生任何变化，此时已经找到各点的最短路径，因此可以提前中止循环，这也是bellman-ford算法常见的一个优化思路。

二、算法代码

def bellman_ford(ori, des, N):
    dist = [float('inf')] * N
    dist[ori] = 0 ## 起始点的距离初始化为0
    ## 进行N-1次循环
    for i in range(N-1):
        ## 每一次循环针对每一个节点更新最短距离
        for j in range(N):
            for k in range(N):
                ## d为距离矩阵
                if dist[j] > dist[k] + d[k][j]:
                    dist[j] = dist[k] + d[i][j]
    return dist[des]

 三、负权回路的判定

        若图中存在负权回路，则意味着部分节点是没有最短路的，因为可以不断的走负权回路获得更短的距离。那么在执行完N-1次操作之后，再进行一次循环，对每个节点的最短距离进行更新，如果更新成功，则意味着图中存在负权回路。

四、总结

        Bellman-Ford算法是一个经典的最短路算法，在学习元启发式算法求解VRP相关问题时遇到了该算法，故而进行了一些学习，并将自己对于该算法的一些理解记录了下来与大家分享，欢迎讨论与指出不足之处！

五、参考博客

(10条消息) 算法系列——贝尔曼福特算法（Bellman-Ford）_lzh1366的博客-CSDN博客

(10条消息) Bellman-ford算法_bellman-ford算法的思想_十七溯的博客-CSDN博客