Shortest Path
本文讨论的是带权有向图，并称路径上第一个顶点为源点(Source)，最后一个顶点为终点(Destination)。
下面是两种最常见的最短路径问题：
- 从某个源点到其余各顶点的最短路径 - Dijkstra算法
- 每一对顶点之间的最短路径 - Floyd算法
Dijkstra算法
Dijkstra算法适用于求从某个源点到其余各顶点的最短路径的问题。
【Dijkstra算法步骤】
【例子】
【详细解释】
Dijkstra算法是基于贪心策略的。
不论是使用邻接矩阵表示，还是带权的邻接表表示，Dijkstra算法的时间复杂度都是O(|V|^2)。
另外，边上带有负权值时，Dijkstra算法并不适用。
Floyd算法
求所有顶点之间的路径的最短路径问题描述如下：已知一个各边权值均大于0的带权有向图，对任意两个顶点vi!=vj，要求求出vi和vj之间的最短路径和最短路径长度。
【Floyd算法的基本思想】
【Floyd算法的算法描述】
【例子以及算法执行过程】
【技巧说明】
- A的上标i表示当前以vi作为中间顶点。
- 对角线数值恒为0；
- 如果以vi为中间顶点，则第i行和第i列的数值都不变；
- 剩余位置的数值为
min(原本的数值, 当前位置投影到第i行对应位置数值和当前投影到第i列对应位置数值之和)。
Floyd算法的时间复杂度为O(|V|^3)。
但是由于Floyd算法的代码很紧凑，且不包含其他复杂的数据结构，因此隐含的常数系数很小，即使对于中等规模的输入来说，它仍然是相当有效的。
【算法的适用范围】
- Floyd算法允许图中有带负权的边，但不允许有包含带负权值的边组成回路。
- Floyd算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。
【该问题的其他解法】
单源最短路径来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负，运行一次Dijkstra算法，其时间复杂度为O(|V|^2) * |V| = O(|V|^3)。