[Algorith]Shortest Path

单源最短路径(无负权边)

Single Source Shortest Path(SSSP)问题。最有名的是Dijkstra算法，适用于没有权值为负的边的SSSP问题。具体的算法是，对于图G(V, E)我们从起始节点s开始，维护集合S，S为已经找到从s到其最短路径的节点。每次我们在V-S中找距离s最短的节点u，放入S，然后更新所有和u相邻并且在V-S当中的节点v到s的距离，如果dist(s, u) + w(u, v) < dist(s, v)，我们更新对应v的值，我们把这一步叫做relax。重复步骤直到S = V。
证明：
假设算法运行当前，下一个要展开的节点是v，最短路径是p。从s到v的路径有两种可能：

1. 其只经过S的节点，最后到达v
2. 其经过S的节点，又经过V-S的某些节点，最后到达v

显而易见，p肯定是满足条件1的最短的路径。假设我们存在满足第二种情况的路径p'，并且p'的长度小于p。那么p'上一定存在一个节点u，它处在S和V-S的交界处，并且在V-S这边，由于所有的边权值为不为负，s经过一部分p'到u的距离，肯定小于等于p'的长度。如果相等，那么我们可以展开u或者v，我们选择展开v肯定没有错。如果小于，那么u应该先于v被展开，那么u应该已经在S当中了，和我们假设的前提矛盾。所以不存在满足条件2的从s到v的路径，其长度小于p的长度。所以p一定是最短路径。

实现的话，我们用优先队列。如果优先队列支持update队列元素的priority的话，时间复杂度O((V + E)* log V)，因为我们对每一个节点要从队列pop，每个边都要做一次relax，也就是可能要做一次优先队列的insert/update，队列长度不超过V。如果优先队列不支持update，那么我们要允许push重复的元素到优先队列里，一旦某个节点被展开了，队列中剩下对于节点的数据就要被跳过。时间复杂度O((V + E) * log E)。代码如下：

单源最短路径(无负权环)

在上面的证明过程可以看出来，对于存在负权边的图，Dijkstra是行不通的。我们需要用Bellman-Ford来解决这类问题。首先可以肯定的是图中不能包含负权环，如果包含负权环的话，那么我们不可能找到最小路径的。因为我们只需要一直沿着环走，路径长度会一直减小，所以我们只讨论不存在负权环的情况。Bellman-Ford的思路是，图中的每一条边e(u, v)，我们都做一次relax操作(见上文)，假设图有N个节点，我们循环N - 1次，如果源节点为s，dist(s, s) = 0, s到其他任意点v， dist(s, v) = +∞：

• from 1 to N - 1
• 对于图中的每一条边e(u, v)
• if dist(s, u) + w(u, v) < dist(s, v), dist(s, v) = dist(s, u) + w(u, v) 

证明：

显而易见的是，对于存在N个节点的图，从s节点开始，到达某个节点v的最短路径最多经过N - 1个节点(包括v不包括s)。因为最短路径是不可能包括环的(无负权环)，所以上述结论是成立的，那么相对的，这条路径最多包含N - 1条边。我们第一次对所有边进行relax的操作，就能找到最短路径包含了一条边的所有路径；第二次对所有边进行relax就可以找到最短路径包含了两条边的所有路径...以此类推，这样的操作进行了N - 1次之后，所有包含了小于等于N - 1条边的最短路径就被我们找到了。因为不存在包含大于N -1条边的最短路径，所以我们找到了所有最短路径，证明完毕。
实现的话就非常简单了，时间复杂度O(V * E)。代码如下：


值得一提的是BF算法还可以帮我们检测负权环。循环N - 1次之后我们已经得到了u到v的最短路径，我们在额外循环一次，如果最短路径变短了，就代表图中存在负权环。

多源最短路径(无负权环)

如果我们想要求图中任意一点u到任意一点v的最短距离，我们应该怎么做呢？这就是Multiple Source ShortestPath(MSSP)问题，那么对于这种问题，我们有Floyd-Warshall算法来解决。FW算法的核心思想仍然是DP，我们定义子问题dp[i][j][k]为，从节点i到j，用{1, 2...k}中的节点当中间节点(中间节点的意思是其不为两端的节点)的情况下的最短路径。这种情况下dp[i][j][k]只有两种可能:

1. 我们考虑不经过节点k的路径，用{1,2...k - 1}当中间节点的最短路径，为dp[i][j][k - 1]
2. 加上节点k之后，只考虑经过节点k的最短路径，其为dp[i][k][k - 1] + dp[k][j][k - 1]

所以我们有了递推公式：

• dp[i][j][k] = min(dp[i][j][k - 1], dp[i][k][k - 1] + dp[k][j][k - 1])

实现的话，乍看之下我们需要三维数组。但其实二维就够用，我们用dp[i][j]表示从{1,2...k}选择中间节点情况下，从节点i到j的最短路径:

• 当k = 1时，显然dp[i][j]就是满足条件的最短路径
• 假设当k = m时，结论成立。那么当k = m + 1的时候，dp[i][j]还没更新的时候，其仍为dp[i][j][k - 1]的值。当我们计算经过k的最短路径的时候dp[i][j] = dp[i][k] + dp[k][j]，其中dp[i][k]和dp[k][j]都不可能有k为其路径上的中间节点。假设k为其中间节点，代表i到k或者k到j的最短路径包含了环，这个只可能是负权环，但题目假设没有负权环，所以矛盾。

这样简化之后代码就变得十分简单了。时间复杂度O(N^3)，空间复杂度O(N^2)。代码如下：

FW算法同样可以帮我们检测负权环，算法跑完之后如果存在dp[i][i]的值小于0，说明图中存在负权环。

最长路径问题

求一个图中的最长路径，路径可以在任意点开始，任意点终止，允许负权边。

不带权的无向无环图

等价于树的直径问题，也就是找到树的最长路径。递归或者从外向内的BFS可以解决。

递归做法：Diameter of Binary Tree

自外向内的BFS：Minimum Height Trees

不带权的有向无环图

自外向内的BFS/拓扑排序：Longest Increasing Path in a Matrix

带权的有向无环图

拓扑排序+DP

带权的无向无环图

DFS找叶子，然后再从叶子开始DFS找最长路径

普遍解法(允许带环但不为正权环)

• 从u到v的最长路径：不能用Dijkstra，因为不满足最优子结构。对于我们维护的S，和下一个展开的节点x，完全有可能存在一条经过S之外的节点到达x的路径可能更长。而且我们也不能把边取反，Dijkstra不能应用于负权边。Bellman Ford任然是可行的，我们把边权值取反，跑BF算法找最短路径，取反之后就是对应的最长路径。
• 多圆最长路径/任意起始终结点的最长路径: Floyd-Warshall算法仍然满足，边权值取反找多源最短路径，取反之后就是最长路径。