4.3 最短路径算法（Dijkstra算法、Bellman-Ford算法、Floyd-War...

文档摘要

4.3 最短路径算法（Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法） 4.3 最短路径算法最短路径算法旨在寻找图中两个节点之间的最短路径。这里的“最短”可以指距离、时间、成本或其他任何可以量化的度量标准。根据图的特性（是否有负权边、是否是有向图等），我们需要选择合适的算法。 4.3.1 Dijkstra算法算法描述： Dijkstra算法是一种用于在带权重的图中寻找单源最短路径的算法。它要求图中没有负权边。该算法使用贪心策略，每次选择当前距离源节点最近的未访问节点，并更新其邻居节点的距离。算法步骤：初始化：创建一个距离数组，用于存储从源节点到每个节点的最短距离。初始时，源节点到自身的距离为 0，到其他节点的距离设为无穷大（表示不可达）。