Question

最短路径专题

Answer 1

参见贪心算法——最短路径Dijkstra算法
参见动态规划

（ 针对单源最短路径问题 ）不失一般性，假定在找到的最短路径中没有环路，即它们都是简单路径。由于图G=(V, E)中的任意无环路径最多包含|V|个不同的结点，它也最多包含|V| - 1条边。

1）三角不等式性质——最短路径的定义

2）上界性质

3）非路径性质

4）收敛性质——最优子结构

5）路径松弛性质

6）前驱子图性质

1）算法描述

2）算法正确性证明

1）算法描述

2）算法正确性证明

3）SPFA算法改进——贪心策略（迅速降低结点的路径，收敛更快）

1）算法描述

2）算法正确性证明

3）PERT图中的关键路径

1）算法描述——广度优先搜索

2）算法正确性证明

1）差分约束系统

2）约束图——从图论的观点来理解差分约束系统

上图对应的约束图为：

3）求解差分约束系统——Bellman-Ford算法

4）求解差分约束系统——Bellman-Ford算法的改进

1）矩阵乘法与EXTEND-SHORTEST-PATHS的对比

2）利用矩阵乘法的思想改进算法