最短路径算法是一个比较常见的用于查找2点之间最短路径的方案。在工作中，由于涉及要查找2点之间的最短路径的场景，所以特此记录一下 算法思想 美国应用数学家Richard Bellman (理查德.贝尔曼, 动态规划的提出者)于1958 年发表了该算法。此外Lester Ford在1956年也发表了该算法。因此这个算法叫做Bellman-Ford算法。 Bellman-Ford算法是一种基于逐次逼近思想进行最短路径求解的算法。其可以被应用在带负权的有向图中，Bellman-ford 算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。缺点是时间复杂度过高，高达O(VE), V为顶点数，E为边数。 其核心思想为：对于任意一个具有n个节点的图 𝐺 ，任意两点之间的最短路径至多包含 𝑛−1 条边。因此我们可以反复通过对边的松弛来得到当前图的最短路径。 也就是说：第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离；第3轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离…… 松弛操作的含义是更新节点之间的最短距离。 分析 第一步：创建一个带权重 (可以有负权) 的有向图 第二步：选定一个起点（A），将A 到所有节点的 距离都置为 无穷大。 第三步：从节点A开始，将节点最短距离更新，比如 A -> B 直接相连，最短距离是 4 ，A->C 直接相连，距离是 2 。 第四步：最差的情况下，我们需要 V （节点个数）次这样的操作。一个节点最短路径需要被调整 V 次。 第五步：注意右上角的节点 D 是怎么调整的，因为 B -> D (4+2) = 6 , C -> D (2+4) =6 , E->D (6-5)=1 ，所以被更新. 第五步：经过最大循环次数 or 所有的顶点都有其路径长度且不再变后，检查是否有负循环。 负环的含义 短路径算法通常用于在加权图中找到两个顶点之间的最短路径。然而，当图中存在负权边时，情况就会变得复杂。负权环（Negative Weight Cycle）是指图中的一个环，其总权重为负值。如果存在负权环，那么最短路径的概念可能会变得模糊，因为你可以无限次地通过这个环来减少路径的总权重。