（3-1）Bellman-Ford算法：Bellman-Ford算法介绍

Bellman-Ford算法是一种用于寻找图中单源最短路径的算法，可以处理带有负权边的图。它通过对所有边进行松弛操作来逐步更新节点的最短路径估计，最多进行|V|-1次迭代，其中|V|是节点数。如果在这些迭代中仍然存在可更新的最短路径，则说明图中存在负权环。算法的时间复杂度为O(V*E)，其中V是节点数，E是边数。在本章的内容中，将详细讲解Bellman-Ford算法在路径规划中的用法，展示这些算法在智能驾驶、无人机和机器人领域中的应用过程。

3.1  Bellman-Ford算法介绍

Bellman-Ford算法是解决单源最短路径问题的一种算法。它的核心思想是通过对所有边进行松弛操作，逐步更新节点的最短路径估计值。

3.1.1  背景与历史

Bellman-Ford算法是一种计算加权有向图中从单个源顶点到所有其他顶点的最短路径的算法，该算法最初由Alfonso Shimbel（1955年）提出，但实际上是以Richard Bellman和Lester Ford Jr.的名字命名的。