问：如何理解最短路算法？
- 答：v1到v2：10为最短路径；
v1到v3：7为最短路径；
v1到v4：8为最短路径；
v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；
v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；
v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；
v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径
Dijkstra：
求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契芦基孝堆作优先队列陪稿的话，算法时间复杂度，锋粗则为O（V*lgV + E）。
以上内容参考：
问：【数据结构】最短路径之迪杰斯特拉(Dijkstra)算法与弗洛伊德(Floyd)算法
- 答：迪兄伏杰斯特拉(Dijkstra)算法核心： 按照路径长度递增的次序产生最短路径。
迪杰斯特拉(Dijkstra)算法步骤：（求图中v0到v8的最短路径）并非一下子求出v0到v8的最短路团尘尘径，而是 一塌禅步一步求出它们之间顶点的最短路径 ，过过程中都是 基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得出源点与终点的最短路径 。
弗洛伊德(Floyd)算法是一个经典的 动态规划算法 。
问：最短路径专题
- 答：参见贪心算法——最短路径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）利用矩阵乘法的思想改进算法
