个人技术分享

相关文章：
数据结构–图的概念
图搜索算法 - 深度优先搜索法（DFS）
图搜索算法 - 广度优先搜索法（BFS）
图搜索算法 - 拓扑排序
图搜索算法-最短路径算法-戴克斯特拉算法

贝尔曼-福特算法（Bellman-Ford）

现在继续学习求解最短路径的第二种算法，首先回想戴克斯特拉算法的例子，每个边的权重都是正整数，若出现负权重，算法能不能正常运行呢？看以下例子，如图所示。

# 运行戴克斯特拉算法
g = DijkstraGraph(['A','B','C','D']) 
g.graph = [[0, 1, 2, 10], 
        [1, 0, 1, -20], 
        [2, 1, 0, 0], 
        [10, -20, 0, 0],
        ]; 
g.dijkstra(0)# A作为源结点
#-------------结果----------------
结点      距离源结点的距离
A        0
B        1
C        2
D        10

结果明显是错误的，大家清楚知道结点【B】到结点【A】最短距离不是1，它可以通过结点【D】到结点【A】，此时最短距离为-10，而且如果能够循环，每次循环距离还能不断缩小，变成一个死循环。既然戴克斯特拉算法没有办法计算负权重问题