最短路径

最短路径（Shortest Path）

在现实中很多需要都运用到了最短路径的算法，例如从一个地铁站到另一个地铁站的最快换乘路线等。地铁线路图中，地铁站可以看作是图的顶点，站与站之间的线路可以看作是边，权重可以是距离、时间、费用等。

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径，这条路径就是两点之间的最短路径。其中最短路径的第一个顶点称为源点（source），最后一个顶点为终点（destination）。

图的最短路径问题分为2种类型：

1. 单源最短路径：从某固定源点出发，求到所有其它顶点的最短路径。

2. 多源最短路径：求任意两顶点间的最短路径。

无权图的单源最短路径算法（SSSP, Single-Source Shortest Path）

无权图的单源最短路径算法可以按照递增（非递减）的顺序找出到各个顶点的最短路，算法类似广度优先遍历。

例如在一个无权图中，以顶点3作为源点，离源点距离为1的顶点有1和6，距离为2的顶点有2和4，距离为3的顶点有5和7。

无权图的单源最短路径算法中，dist[v]存储从源点S到v的最短路径，初始化源点dist[S]的距离为0，path[v]表示达到顶点路径v上一个经过的顶点。

无权图的单源最短路径

unweightedSSSP(Vertex S)
    dist[S] = 0; dist[other vertices] = -1; path[*] = NULL
    enqueue(Q, S)
    while !isEmpty(Q)
        V = dequeue(Q)
        for v in neighbors(V)
            if dist[v] == -1
                dist[v] = dist[V] + 1
                path[v] = V
                enqueue(Q, v)

有权图的单源最短路径算法

有权图的最短路径不一定是经过顶点数最少的路。如果图中存在负值圈（negative-cost cycle）的话会导致算法失效，因为沿着回路走无穷多次，花销是负无穷。

边权非负的带权图，单源最短路径可以通过迪杰斯特拉（Dijkstra）算法解决；有负权边时不能直接使用Dijkstra算法。

特斯拉？什么鬼？

迪杰斯特拉算法的本质是不断刷新起点与其他各个顶点之间的距离表。Dijkstra算法采用了贪心的思想，每次从未收录的顶点中选取dist值最小的收录。每当收录一个顶点时，可能会影响另外一个顶点的dist值。

例如计算从源点A到其它各顶点的最短路径。

第1步：创建距离表。其中表中key是顶点名称，value是源点A到对应顶点的已知最短距离。一开始并不知道最短路径是多少，因此除源点A的value为0之外，其余value都为$\infty$。

第2步：找到源点A的邻接点B和C，从A到B的距离是5，从A到C的距离是2。

第3步：从距离表中找到从A出发距离最短的顶点，也就是顶点C。找到顶点C的邻接点D和F（A已经遍历过不需要考虑）。从C到D的距离是6，所以从A到D的距离是2 + 6 = 8；从C到F的距离是8，所以从A到F的距离是2 + 8 = 10。

第4步：从距离表中找到从A出发距离最短的顶点（C已经遍历过不需要考虑），也就是顶点B。找到顶点B的邻接点D和E（A已经遍历过不需要考虑）。从B到D的距离是1，所以从A到D的距离是5 + 1 = 6，小于距离表中的8；从B到E的距离是6，所以从A到E的距离是5 + 6 = 11。

第5步：从距离表中找到从A出发距离最短的顶点（B和C不用考虑），也就是顶点D。找到顶点D的邻接点E和F。从D到E的距离是1，所以从A到E的距离是6 + 1 = 7，小于距离表中的11；从D到F的距离是2，所以从A到F的距离是6 + 2 = 8，小于距离表中的10。

第6步：从距离表中找到从A出发距离最短的顶点，也就是顶点E。找到顶点E的邻接点G。从E到G的距离是7，所以从A到G的距离是7 + 7 = 14。

第7步：从距离表中找到从A出发距离最短的顶点，也就是顶点F。找到顶点F的邻接点G。从F到G的距离是3，所以从A到G的距离是8 + 3 = 11，小于距离表中的14。

最终，距离表中存储的是从源点A到所有顶点的最短距离。

多源最短路径算法

如何能够求出一个带权图中所有顶点两两之间的最短距离呢？

对了！刚刚学过了Dijkstra算法，可以对每个顶点都使用一次Dijkstra算法，这样就求出了所有顶点之间的最短距离。

这个思路确实可以实现，但是Dijkstra算法的代码逻辑比较复杂，有没有更简单的方法呢？

在没有负权回路的前提下，弗洛伊德（Floyd-Warshall）算法是专门用于寻找带权图中多源点之间的最短路径算法。Floyd算法的思想是，若想缩短两点间的距离，仅有一种方式，那就是通过第三顶点绕行。

假设$D^k[i][j]$为路径$\{i \rightarrow \{l \le k\} \rightarrow j\}$的最小长度。当$D^{k-1}$已经完成，递推到$D^k$时：

1. 如果$k \notin \text{最短路径}\{i \rightarrow \{l \le k\} \rightarrow j\}$，则$D^k[i][j] = D^{k-1}[i][j]$。

2. 如果$k \in \text{最短路径}\{i \rightarrow \{l \le k\} \rightarrow j\}$，该路径必定由两段最短路径组成。综合两种情况，应取原路径与经过k的路径中较短者：$D^k[i][j] = \min(D^{k-1}[i][j], D^{k-1}[i][k] + D^{k-1}[k][j])$。

例如，小哼准备去一些城市旅游，有些城市之间有公路，有些城市之间则没有。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之间的最短路程。

如果要让任意两点之间的路程变短，只能引入第三个点，并通过这个顶点中转才有可能缩短原来的路程。这个中转的顶点甚至有时候不只通过一个顶点，而是经过两个或更多点中转会更短。

当任意两点之间不允许经过第三个点中转时，这些城市之间的最短路径就是邻接矩阵的初始路径。

在只允许经过1号顶点中转的情况下，任意两点之间的最短路程更新为：

在只允许经过1号和2号顶点中转的情况下，任意两点之间的最短路程更新为：

在只允许经过1号、2号和3号顶点中转的情况下，任意两点之间的最短路程更新为：

最后允许通过所有顶点作为中转，任意两点之间的最短路程更新为：

Floyd最短路径

floyd(Graph G)
    for k = 0 to G.vertexNum - 1
        for i = 0 to G.vertexNum - 1
            for j = 0 to G.vertexNum - 1
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])