Python中Bellman算法在图论纵横对比中的应用有何特点？

本文共计6881个文字，预计阅读时间需要28分钟。

1. 前言：无需方向、无加权图的任意顶点间的最短路径由顶点间的边数决定，可直接使用原始定义的宽度优先搜索算法查找。但不论是有向还是无向，只要存在加权图，最短路径由边的权重决定。

1. 前言

因无向、无加权图的任意顶点之间的最短路径由顶点之间的边数决定，可以直接使用原始定义的广度优先搜索算法查找。

但是，无论是有向、还是无向，只要是加权图，最短路径长度的定义是：起点到终点之间所有路径中权重总和最小的那条路径。

如下图所示，A 到 C 的最短路径并不是 A 直接到 C（权重是 9），而是 A 到 B 再到 C（权重是 7）。所以，需要在广度优先搜索算法的基础上进行算法升级后才能查找到。

加权图的常用最短路径查找算法有：

• 贝尔曼-福特（Bellman-Ford）算法
• Dijkstra（迪杰斯特拉） 算法
• A* 算法
• D* 算法

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

贝尔曼-福特算法取自于创始人理查德.贝尔曼和莱斯特.福特，本文简称 BF 算法

BF 算法属于迭代、穷举算法，算法效率较低，如果图结构中顶点数量为 n，边数为 m ，则该算法的时间复杂度为 m*n ，还是挺大的。