README.
# 最短路径
最短路径问题是我们在图论中经常碰到的问题之一，其通用可以描述为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA 算法，另外还有著名的启发式搜索算法 A*，其中 Floyd 算法可以求解任意两点间的最短路径的长度。笔者认为任意一个最短路算法都是基于这样一个事实：从任意节点 A 到任意节点 B 的最短路径不外乎 2 种可能，1 是直接从 A 到 B，2 是从 A 经过若干个节点到 B。最短路径问题可以进一步分为单源最短路径和全源最短路径。
-
单源最短路径定义为，给定起始顶点 s，找出从 s 到图中其它各顶点的最短路径。求解单源最短路径的算法主要是 Dijkstra 算法和 Bellman-Ford 算法，其中 Dijkstra 算法主要解决所有边的权为非负的单源最短路径问题，而 Bellman-Ford 算法可以适用于更一般的问题，图中边的权值可以为负。
-
全源最短路径定义为，找出连接图中各对顶点的最短路径。求解全源最短路径的算法主要有 Floyd 算法和 Johonson 算法，其中 Floyd 算法可以检测图中的负环并可以解决不包括负环的图中的全源最短路径问题；Johonson 算法同样也是解决不包含负环的图的全源最短路径问题，但是其算法效率更高。
最优子结构
最短路径算法具有最短路径的最优子结构性质，也就是两顶点之间的最短路径包括路径上其它顶点的最短路径。具体描述为：对于给定的带权图 G=(V, E)，设p=<v1, v2, …,vk>是从 v1 到 vk 的最短路径，那么对于任意 i 和 j，1≤i≤j≤k，pij=<vi, vi+1, …, vj>为 p 中顶点 vi 到 vj 的子路径，那么 pij 是顶点 vi 到 vj 的最短路径。最短路径算法都使用了松弛(relaxation)技术。开始进行一个最短路径算法时，只知道图中边和权值。随着处理逐渐得到各对顶点的最短路径的信息。算法会逐渐更新这些信息，每步都会检查是否可以找到一条路径比当前给定路径更短。这一过程通常称为“松弛”。如图为单元最短路径算法的松弛操作。问题为求求解顶点 s 到图中各顶点之间的最短路径，用 d[i]表示顶点 s 到顶点 i 的最短路径的长度。对权值为 1 的边(v, w)进行松弛，若当前到顶点 v 和 w 的最短路径的长度分别 6 和 8，如图(a)，则此时 d[w]<d[v]+ ω(v, w)，所以对 d[w]的值需要减小，并且 s 到顶点 w 的最短路径为顶点 s 到 v 的最短路径，再经过边(v, w)，如图(b)。
我们用 d[i]数组表示顶点 s 到顶点 i 的最短路径的长度，用 p[i]表示顶点 i 在最短路径中的父顶点。可以将边松弛过程用一下代码来描述：
Relax(v, w, ω(v, w))
if d[w]>d[v] + ω(v, w)
{d[w]=d[v] + ω(v, w); p[w] = v;}