两点间小于指定长度的所有路径组成的子图

Question

最近在做网络分析，问题是这样的，给定一个有环有向图G，指定路径的起点S和终点E，限制路径的长度最多为t，求得所有从S出发终止于t的长度最多为t的所有路径组成的子图G_sub。如下图所示

S到E的长度最多为3的路径组成的子图是由红色、蓝色和绿色顶点及其之间连接的边组成的图。那么如何在原图中找出这一子图？

Answer 1

有时技巧就出自一瞬之间的想法。

1. 先从原点S出发，求一次单源最短路径。
2. 再把所有的边全都翻过来，从汇点E出发，求一次单源最短路径。
3. 则对每个点I，都得到了S->I的最短路径长度L(S, I)，和I->E的最短路径长度L(I, E)。则经由I点的S->I->E的最短路径长度为：L(S, I) + L(I, E)。
4. 如果L(S, I) + L(I, E) <= tmax，则必然存在一条经由I点的S->I->E的路径，符合长度要求。（肯定条件按题设，只需证明存在性）此时I必然是所求子图的一部分。
5. 反过来看，如果L(S, I) + L(I, E) > tmax，则所有经由I点的S->I->E的路径，全都不符合长度要求。（否定存在性，必须证明必然性）则I必然不是所求子图的一部分。
6. 正反两方面得到证明，判断依据就有了。子图包含哪些点也就有了。

这个算法可以用在任意没有负权回路的有向加权图上。

点好确定，但比较罗嗦的是边怎么办。因为最短路径解决这个问题，终究是一个存在性的答案。如果只把涉及的点的最短路径包含进来，必然丢边，因为非最短路径也会可行。例如下图，如果t>=11，则10符合条件，但按最短路径算就肯定被仍掉：

但又不能把这些点之间的所有边全都算进来。同样是这个图，如果t<11，则把10包含进来就算错，因为经由10的路径此时就不可能在t的限制内达到终点E。

不过用和前边算法相同的思路，略微再改一改，就能确定每条边是否在所求子图内：

1. 可以先剪枝，子图这些点之外的边全部不考虑。
2. 审查连接子图内两点的每一条边U->V，权值记为W(U, V)。
3. 则经由U->V边，即S->U->V->E的最短路径长度为：L(S, U) + W(U, V) + L(V, E)。
4. 同样的道理，如果L(S, U) + W(U, V) + L(V, E) <= tmax，则U->V边肯定包含在子图内。（存在性）
5. 如果L(S, U) + W(U, V) + L(V, E) > tmax，则U->V边一定不包含在子图内。（必然性）
6. 得出那些边可以包含在子图内。

边和点都有了，子图就出来了。算法复杂度为：

• 求点：（优化算法）Johnson's Algorithm，O(V^2logV + VE)；（朴素算法）Floyd-Warshall Algorithm，O(V^3)；（对无负权边的图）Dijkstra's Algorithm，朴素O(V^2)，二项堆优化O(E+VlogV)。
• 求边：扫描，O(E)

最后总体的最优复杂度为：O(V^2logV + VE)，对稠密图接近O(V^3)。
对无负权边的图最优为：O(E+VlogV)，对稀疏图接近O(VlogV)。
所以具体效率，还看具体问题中图的形态而定。