动态规划(4)详细讲解各最短路径算法及比较1 最短路径问题（The shortest-path problem, SPP）2 Dijkstra(迪杰斯特拉)算法Floyd-Warshall算法（动态规划）Bellman-Ford（动态规划）A*算法次最短路径其他

75 阅读 0 评论 50 点赞

我是靠谱客的博主健康保温杯，最近开发中收集的这篇文章主要介绍动态规划(4)详细讲解各最短路径算法及比较1 最短路径问题（The shortest-path problem, SPP）2 Dijkstra(迪杰斯特拉)算法Floyd-Warshall算法（动态规划）Bellman-Ford（动态规划）A*算法次最短路径其他，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1 最短路径问题（The shortest-path problem, SPP）

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两结点之间的最短路径。算法具体的形式包括：

1) 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。

2) 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

3）确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。

4）全局最短路径问题 - 求图中所有的最短路径。

最短路径在导航中有重要应用，如从出发地到目的地的最短路径，从救灾处到受灾处的最短路径等。

各最短路径算法比较

2 Dijkstra(迪杰斯特拉)算法

2.1 定义

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。

2.2 算法描述

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径长度值被赋为 0 （d[s] = 0），若存在能直接到达的边（s,m），则把d[m]设为w（s,m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 和上述 m 外 d[v] = ∞）。当算法退出时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 u 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当d[u] 达到它最终的值的时候每条边（u, v）都只被拓展一次。

算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边 (u, v) 进行拓展。