algorithm - 预处理竞争中的最短路径

Question

很容易证明，如果P是u和v之间的最短路径，那么每条子路径也是最短路径。给定一个连通图，我想预处理矩阵中每对节点之间的最短路径，这样:

1. 路径[u,v] = 路径[v,u]
2. 如果 x,y 在 Path[u,v] 中，则 Path[x,y] 是 Path[u,v] 的子路径。

我想不出算法或证明，实际上我不知道这是否可行。欢迎任何想法。谢谢。

Answer 1

如果你正在使用无向图，或者如果保证弧 (a, b) 的权重等于所有弧中的弧 (b, a) 的权重，你只能得到 (1)你的图表。

您描述的问题听起来像是全对最短路径问题:对于连通图中的每对节点，找到该对节点之间的最短路径。 Floyd-Warshall 算法可用于查找路径的长度，并且可以直接从那里重建最短路径。

该算法进一步要求没有负循环(否则通过再次运行该循环总是可以获得更短的路径)但该要求似乎是合理的。

为了保证属性 (2)，您需要确保在重构​​路径时，只要可能有不止一条最短路径，您就是在重构“规范”路径。为此，对顶点进行排序并始终按升序测试候选节点，始终优先选择保持最短路径属性的最低阶节点。

维基百科有一篇相当不错的文章。