Python中Bellman-Ford与Dijkstra算法在图结构上的性能差异对比是怎样的？

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

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 ，还是挺大的。

理论上讲，图结构中边上的权重一般用来描述现实世界中的速度、时间、花费、里程……基本上都是非负数。即使是负数，BF 算法也能工作得较好。

2.1 BF 算法思想

问题：如下图，搜索 A 到其它任意顶点之间的最短路径。