#最短路径

最短路径问题是我们在图论中经常碰到的问题之一，其通用可以描述为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，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;}

Links

• 彻底弄懂最短路径问题

• 6.3.3最短路径算法–Dijkstra算法，Bellmanford算法，Floyd算法，Johnson算法

• SPFA算法学习笔记