最短路径 Shortest Path

# 最短路径 Shortest Path

加权有向图中每条路径都有值，其值是该路径上所有边的权值之和。最短路径（Shortest Path）问题就是指求出两个给定顶点间权值最小的路径。

# 定义

两个顶点 s 和 t 之间的一条最短路径是从 s 到 t 的一条有向简单路径，而且此路径具有以下的性质：不存在另一条这样的路径且有更小的权值。

# 最短路径树（Shortest-path trees，简称 SPT）

给定一个图和一个指定的顶点 s，则 s 的最短路径树是一个包含 s 以及由 s 可达的所有顶点的子图，它构成以 s 为根的一棵有向树，其中每条树路径都是图中的一条最短路径。最短路径树定义了从根到其它顶点的最短路径。

# 分类

图中最短路径问题主要是以下三类:

源点－汇点最短路径
单源最短路径
全源最短路径

# 算法

求图中最短路径的算法常用的有：

Dijkstra 算法
Floyd-Warshall 算法
Bellman-Ford 算法

###　基本操作

# 边松弛（edge relaxation）

检查一条给定的边，是否可以通过该边，对到其所指顶点的最短路径进行更新。

不妨设有条边 e=(u,v) ，它的长度是 e.dist ， d[i] 表示源点到顶点 i 的最短距离，则松弛操作如下： if (d[v] > d[u] + e.dist) d[v] = d[u] + e.dist 上式的意思就是：如果从源点到 u 的最短距离加上 u 到 v 的长度小于当前源点到 v 的最短距离，那么更新源点到 v 的最短距离。边松弛体现在 Dijkstra 算法和 Bellman-Ford 算法中

# 路径松弛（path relaxation）

检查一个给定顶点，是否可以使得连接另外两个给定顶点的最短路径进行更新。

不妨设现在有一个顶点 x，还有另外两个顶点 s 和 t。考虑能否通过 x，使得 s 到 t 的最短距离变的更小，能的话，就进行路径松弛： if (d[s][t] > d[s][x] + d[x][t]) d[s][t] = d[s][x] + d[x][t] 上式的意思是：如果 s 到 x 的最短距离加上 x 到 t 的最短距离小于 s 到 t 的最短距离，那么更新 s 到 t 的最短距离。路径松弛体现在 Floyd-Warshall 算法中。

# Dijkstra 算法

Dijkstra 算法计算单源最短路径，它的基本思想：开始把源点放在 SPT 中，然后，每次增加一条边来构造 SPT，所取的边总是可以给出从源点到尚未在 SPT 中的一个顶点的最短路径。也就是说，按照顶点与起始顶点的距离（通过 SPT）为顺序来加入顶点。即：每次选不在 SPT 中距离源点最近的点加
入 SPT。

# 具体步骤

初始化：顶点集 S 只包含源点，即 S={v}，顶点集 U 包含除 v 外的其他顶点。
从 U 中选取一个顶点 u，它是源点 v 到 U 中最短路径长度最小的顶点，然后把顶点 u 加入 S 中（此时求出了源点 v 到顶点 u 的最短路径长度）。
以顶点 u 为新考虑的中间点，修改顶点 u 的出边邻接点 j 的最短路径长度，此时源点 v 到顶点 j 的最短路径有两条，即一条经过顶点 u，一条不经过顶点 u。
重复步骤 2 和 3，直到 S 包含所有的顶点即 U 为空。

# 基于堆的 Dijkstra 算法代码

	struct Edge {
	int from, to, dist;
	Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
	};
	struct HeapNode {
	int d, u; //d 表示该点到源点的距离，u 是该点的编号
	bool operator< (const HeapNode& rhs) const {
	return d > rhs.d;
	} // 小根堆
	};
	vector<Edge> edges; //edges 存所有的边的信息
	vector<int> G[MAXN]; // G [i] 是顶点 i 发出的所有边
	bool done[MAXN]; // 是否已经加入 SPT
	int d[MAXN]; // 每个点到源点的最短路径
	int p[MAXN]; // 记录到顶点 i 的是哪条边
	void Dijkstra(int s, int V) { // 计算所有顶点到顶点 s 的最短路径
	priority_queue<HeapNode> Q;
	for(int i = 0; i < V; ++i) d[i] = INF;
	d[s] = 0; // 顶点 s 做源点
	memset(done, 0, sizeof(done));
	Q.push((HeapNode){0, s});
	while (!Q.empty()) {
	HeapNode x = Q.top(); Q.pop;
	int u = x.u; // 把出队的队头元素的标号给 u
	if (done[u]) continue; // 已经在 SPT 中就跳过
	done[u] = true; // 标记 u 在 SPT 中了
	for (int i = 0; i < G[u].size(); ++i) {
	Edge& e = edges[G[u][i]];
	if (d[e.to] > d[u] + e.dist) {
	d[e.to] = d[u] + e.dist;
	p[e.to] = G[u][i];
	Q.push((HeapNode){d[e.to], e.to});
	}
	}
	}
	}

# 注意

Dijkstra 算法可以解决带有非负权值的单源最短路径问题，如果图中有负权值，则该算法不成立，因为它的前提是增加更多边时，路径的长度不会递减。

# 分析

利用优先队列实现的 Dijkstra 算法的时间复杂度是 $O(ElogV)$ ，因为它是在一个规模最大是 V 的优先队列中进行 V 个插入，V 个删除最小值，以及 E 个减少键值的操作。

# Floyd-Warshall 算法

Floyd-Warshall 算法计算全源最短路径，它的本质是动态规划，用 d[i][j][k] 表示 i 到 j 的最短距离，而且该路径上的顶点的标号都小于等于 k (除了源点和汇点)，那么下面的式子明显成立： d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

i 到 j 中间标号最大是 k 的路径肯定是这样得到的：

i 到 j，而且中间标号最大是 k-1 的最短路径，或者
i 到 k，中间标号最大是 k-1 的最短路径加上了 k 到 j，中间最大标号是 k-1 的最短路径。这两种情况里的小的就是要求的。

这样就有了 $O(V^3)$ 的算法：

	int d[MAXN][MAXN]; // 距离矩阵
	int p[MAXN][MAXN]; // 路径数组
	void FloydWarshall(int V) {
	// 初始化距离矩阵
	for (int i = 0; i < V; ++i) {
	for (int j = 0; j < V; ++j) {
	if (i == j) {
	d[i][j] = 0; // 同一顶点的距离为 0
	} else {
	d[i][j] = INF; // 不直接相连的顶点的距离设为无穷大
	}
	p[i][j] = -1; // 初始化路径数组
	}
	}

	// 根据边的信息更新距离矩阵
	for (int i = 0; i < edges.size(); ++i) {
	Edge& e = edges[i];
	if (d[e.from][e.to] > e.dist) {
	d[e.from][e.to] = e.dist;
	p[e.from][e.to] = e.from;
	}
	}

	// 计算最短路径
	for (int k = 0; k < V; ++k) {
	for (int i = 0; i < V; ++i) {
	for (int j = 0; j < V; ++j) {
	if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
	d[i][j] = d[i][k] + d[k][j]; // 更新最短路径
	p[i][j] = p[k][j];
	}
	}
	}
	}
	}

# Bellman-Ford 算法

Bellman-Ford 算法计算单源的最短路径。

# 基本思路

为了计算一个从顶点 s 出发的最短路径，用 d[i] 表示源点 s 到 i 的最短路径，开始 d[s] = 0 ，其它都是极大值，然后以任何顺序对每条边进行边松弛操作，完成 V-1 遍这样的操作，就可以得到各点到 s 的最短距离。

我们可以用一个 FIFO 队列来保存这些顶点，每一遍处理的时候只检查这些顶点发出的边，对于沿着一条发出边进行松弛时可能有效的所有顶点都放在一个队列中，每次从队列中取一个顶点，并沿着它的所有边进行松弛。如果其中任何一条边导致到达某个顶点的一条更短的路径，那么将该点放入队列中。

# 基于 FIFO 队列的 Bellman-Ford 算法

	bool bellman_ford(int a) {
	queue<int> Q; // FIFO 队列
	memset(inq, 0, sizeof(inq));
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < n; ++i) d[i] = INF;
	d[s] = 0;
	inq[s] = true; //inq [i] = true，表示顶点 i 在队列里
	Q.push(s);
	while (!Q.empty()) {
	int u = Q.front(); Q.pop();
	inq[u] = false; //u 出队了，就不在队列里了
	for (int i = 0; i < G[u].size(); i++) {
	Edge& e = edges[G[u][i]];
	if (d[u] < INF && d[e.to] > d[u] + e.dist) {
	d[e.to] = d[u] + e.dist;
	p[e.to] = G[u][i];
	if (!inq[e.to]) { // 如果 e.to 不在队列里才入队，否则，不用再入队
	Q.push(e.to);
	inq[e.to] = true;
	if (++cnt[e.to] > n) return false;
	}
	}
	}
	}
	return true;
	}

# 负环

利用 Bellman-Ford 算法很容易来检查一个图是否存在负环。因为最多进行 V-1 遍所有边的松弛操作，所以 V-1 遍后看，是否有新的元素入队？有，就存在负环；否则，则没有。上述代码最后返回 true 就是无负环，返回 false 就是有负环。用 FIFO 队列不好判断哪些是一遍的操作，所以用了 cnt 数组， cnt[i] 表示顶点 i 入队几次了，反正如果无负环， cnt[i] 不会超过 n，否则，最后必超过（可能是超过 V-1 遍操作后）。

Floyd_Warshall 算法也能判断图中是否有负环，只要最后检查是否有 d [i][i] 是负的。上面程序最坏情况下运行时间仍和 VE 成正比，对于稠密图，运行时间可能不比 Floyd 好，对于稀疏图则最快可能快 V 倍。注意 Floyd 只能求所有的最短路径，不会因为你是求某点出发的最短路径而可以减少运行时间。实战中利用 FIFO 队列实现的 Bellman-Ford 算法效果相当好。

目前对于求有负环的最短路径是 NP 困难的。