部分所有对最短路径

Question

给定一个包含许多节点的无向​​加权图，如何计算所有对最短路径的子集？

子集是指图中的一些节点，而不是全部（图的顶点子集，可以手动指定，也可以通过某种聚类算法指定。所选顶点的数量可能是总数的1%~5%顶点）。

Dijkstra 或 Floyd-Warshall 可能会计算额外的节点，这对于我的应用程序来说可能不够高效。

是否有算法可以计算特定节点之间的所有对最短路径并产生良好的性能？

Answer 1

基本上，我认为您不能只考虑某些节点，因为子图中的最短路径可能不是全局最短的。所以你必须考虑所有的节点。

也许你可以像这样实现 Dijkstra 算法：在每次迭代中设置一个检查子例程。如果所有需要的节点都已固定（已找到最小路径），则终止算法。这将为其余节点节省时间。

为了提高效率，如果没有负边长度，我建议使用 n 次 Dijkstra 算法。如果有，请使用约翰逊算法，该算法提供特殊的重新加权技术，将负边长度转换为非负边长度。

也许您只是需要更快的服务器。

希望有帮助。