[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)。代码如下：

	void dijkstra(vector<vector<int>>& edges, int N, int K) {
	vector<vector<pair<int, int>>> g(N + 1);
	unordered_map<int, int> visited;
	//construct graph
	for (auto& edge : edges)
	{
	int u = edge[0], v = edge[1], w = edge[2];
	g[u].emplace_back(v, w);
	}
	//dijkstra
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.emplace(0, K);
	while (pq.size())
	{
	auto p = pq.top();
	int u = p.second, dist = p.first;
	pq.pop();
	if (visited.find(u) != visited.end())continue;
	visited[u] = dist;
	for (auto& e : g[u])
	pq.emplace(dist + e.second, e.first);
	}
	}

view raw dijkstra.cpp hosted with ❤ by GitHub

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

在上面的证明过程可以看出来，对于存在负权边的图，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)。代码如下：

	int bellman_ford(int N, int u, int v, vector<vector<int>>& edges)
	{
	int M = edges.size();
	vector<int> dist(N, INT_MAX);
	dist[u] = 0;
	for(int i = 1; i < N; ++i)
	{
	for(int j = 0; j < M; ++j)
	{
	int from = edges[j][0], to = edges[j][1], weight = edges[j][2];
	if(dist[from] + weight < dist[to])dist[to] = dist[from] + weight;
	}
	}
	return dist[v];
	}

view raw Bellman_Ford.cpp hosted with ❤ by GitHub

值得一提的是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)。代码如下：

	#include <bits/stdc++.h>
	using namespace std;
	vector <int> floyd(int n, vector < vector<int> > edges, vector < vector<int> > queries) {
	//DP[i][j][k] represents shortest path from i to j using first k nodes as intermediate nodes
	//DP[i][j][k] = max(DP[i][j][k - 1], DP[i][k]][k - 1] + DP[k][j][k - 1])
	//We can use just use two dimensional array, since if there is no negative
	//cycle in graph, every time we pick node k as intermediate node, path
	//DP[i][k] and DP[k][j] should not have k as there intermediate node,
	//which satisfy the dp function.
	//Otherwise there will be cycle in shortest path and that can only be
	//negative cycle. And that give us a way to check if there is negative
	//cycle in graph. If there is any dp[i][i] < 0, then there is negative
	//cycle in graph
	const int INF = 1000000;
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
	for(int i = 1; i <= n; ++i)dp[i][i] = 0;
	for(auto& edge : edges)dp[edge[0]][edge[1]] = edge[2];
	for(int k = 1; k <= n; ++k)
	{
	for(int i = 1; i <= n; ++i)
	{
	for(int j = 1; j <= n; ++j)
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	}
	}
	vector<int> res;
	for(int i = 0; i < queries.size(); ++i)
	res.push_back(dp[queries[i][0]][queries[i][1]] == INF? -1: dp[queries[i][0]][queries[i][1]]);
	return res;
	}
	int main() {
	int n;
	int m;
	cin >> n >> m;
	vector< vector<int> > edges(m,vector<int>(3));
	for(int edges_i = 0;edges_i < m;edges_i++){
	for(int edges_j = 0;edges_j < 3;edges_j++){
	cin >> edges[edges_i][edges_j];
	}
	}
	int q;
	cin >> q;
	vector< vector<int> > queries(q,vector<int>(2));
	for(int queries_i = 0;queries_i < q;queries_i++){
	for(int queries_j = 0;queries_j < 2;queries_j++){
	cin >> queries[queries_i][queries_j];
	}
	}
	vector <int> result = floyd(n, edges, queries);
	for (ssize_t i = 0; i < result.size(); i++) {
	cout << result[i] << (i != result.size() - 1 ? "\n" : "");
	}
	cout << endl;
	return 0;
	}

view raw hackerrank_Floyd : City of Blinding Lights.cpp hosted with ❤ by GitHub

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算法仍然满足，边权值取反找多源最短路径，取反之后就是最长路径。