前言：

        最近一直在看《算法导论》。算法这块难啃的硬骨头，向来令我头疼不已，尤其是图算法这一部分愈发觉得难啃。在冥思苦想几日之后虽不能说豁然开朗，但也算是小有斩获，稍加整理思绪之后便有此文。所以以下的内容呢，源于我在阅读《算法导论》期间对自己思考过程的总结。

        言归正传，今天我要说的主题是单源最短路径问题。比如说，你想知道怎样应该怎样从武汉去北京，那么你可以拿起你的手机登陆Google Maps，输入起点武汉，终点北京，Google会告诉你最佳的选择。撇开交通工具的差异（如果是飞机，估计您老就按照两点之间，线段最短的路径直接飞过去了），我们把地图上每一个城市想象成一个点，从一个城市去另一个城市的公路想象成一条线，那么怎样从武汉去北京的问题就变成怎样从起点经过这么多条不同的线路抵达终点的问题了。那么在如此错综复杂的地图上，我们应该如何寻求两点之间的最短路线呢？

        很遗憾的是，当前还没有单纯的解决地图上从A点去B点最短路线的问题，我们往往需要求出从A点出发到所有地方的最短线路之后，才能确定从A到B的最短路线。这是一个很令人头疼的问题，你想如果我们从武汉去北京，犯得着思考怎样从武汉去广州吗？所以说目前的单源最短路径算法在这个境遇上显得十分笨拙。（其实这个问题被我严重化了，可以通过很简单的剪枝避免大量重复的计算）。

思考：

        解决单源最短路径最通用的算法是Dijkstra算法，但是在此之前，我们还是先从Bellman-Ford算法说起。毕竟历史的轨迹是如此发展的，先有Bellman-Ford算法，后才有Dijkstra的改进算法。这样的顺序也方便于我们思考：解决同一个问题，我们是否能做得更好。

        在正式进入出题之前，我们先给定单源最短路径问题的形式化定义：给定一个带权有向图G=(V, E)，对于任意边(u, v)∈E，加权函数ω：E→R赋予边(u, v)一个实数权值ω(u,v)。计算出从给定源点s到图中其余顶点的最短路径。

        另外对数据结构还有一些补充。对于任意顶点v∈V，除了存储顶点v至其邻接顶点的边之外，还存储了从源点s到顶点v的最短路径p=<s, v0, v1, …, vk, v>中v的前驱顶点vk和p的路径长度，分别用π[v]和d[v]表示，即π[v]=vk，d[v]=ω(p)。对于从源点到s到顶点v的最短路径，我们只用从顶点v递归寻找其前驱顶点，到s终止时即为其最短路径。我们用δ(s, v)表示从源点s到顶点v的最短路径长度。

对于这张图，我们设定源点为s，图中被阴影加粗的边都是最短路径所经过的边，

顶点内部的数值代表了其最短路径长度。

例如从s到z的最短路径p=<s, t, y, x, z>，其最短路径长度δ(s, z)=11

        Bellman-Ford算法的基底来自于动态规划。根据《算法导论》中总结出是否能运用动态规划的两点特征：最优子结构和重叠子问题。我们可以证明最短路径问题是可以使用动态规划的，以下将用Cut & Paste这一技术来证明最短路径问题满足最优子结构。

        最短路径的子路径也是最短路径： 假设p=<v1, v2, ...,vn>是从v1到vn的最短路径，对于任意i, j，其中1 ≤ i ≤ j ≤ n，那么在路径p中从顶点vi到顶点vj的子路径也是从vi到vj的最短路径。

        我们把最短路径p分解为v1→vi→vj→vn，考虑从vi到vj的路径q，如果存在另外一条路径q'的路径长度比最短路径p中vi→vj的路径长度还要小，那么我们只用将这条路径q'替换掉原有最短路径p中vi→vj的部分，即可构造一个更短的路径。但这与我们假设p是从v1到vk的最短路径的前提矛盾，所以上述结论成立。至于重叠子问题就更好理解了，如果我们要求从v1到vk的最短路径，那么我们也需依次求出从v1到v2, v3, ..., vk-1的最短路径，每一次求解的过程中都会出现重叠的子问题。

        在具体讲解Bellman-Ford算法之前，我们先引入三角不等式。因为正是通过不断的判定三角不等式是否成立，我们才能确切的求出从源点到图中每个顶点的最短路径。

        三角不等式：对任意边(u, v)∈E，有δ(s, v) ≤ δ(s, u)+ ω(u, v)。

        我们很容易就能证明三角不等式成立。对于从源点s到顶点v的最短路径p，假如存在另外一条经过顶点u到达v的路径p‘，并且p’比原有的最短路径p的路径长度更短，这就与最短路径的前提矛盾，所以不等式必然成立。我们在算法执行过程中始终维持三角不等式成立，并且不断修正顶点v∈V中d[v]和π[v]的值，继而求出最短路径，我们称这样的步骤为松弛（Relax），以下为松弛步骤的伪代码：

Relax(u, v, ω)
{
      if d[v]> d[u] + ω(u, v)
           then d[v] ← d[u] + ω(u, v)
                π[v] ← u
}