algorithm - 部分所有对最短路径

Question

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

子集是指图中的一些节点，而不是全部(图的顶点的子集，可以手动指定，或者来自一些聚类算法。所选顶点的数量可能是1%~5%的总顶点数)。

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

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

Answer 1

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

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

为了效率，如果没有负边长，我推荐使用n次Dijkstra算法。如果有，请使用 Johnson 算法，该算法提供了一种特殊的重新加权技术，可将负边长转换为非负边长。

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

希望对您有所帮助。