给定一个包含许多节点的无向加权图，如何计算所有节点最短路径的子集? 子集意味着图中的一些节点，而不是全部节点（图的顶点子集可能会被手动指定，也可能来自某些聚类算法。所选顶点的数量可能是总顶点的1%~5%）。 Dijkstra或Floyd-Warshall算法可能会计算额外的节点，这对我的应用程序可能不够高效。 是否有算法可以在特定节点之间计算所有对之间的最短路径，并获得良好的性能结果？
基本上，我认为您不能只考虑一些节点，因为子图中的最短路径可能不是全局最短路径。所以您必须考虑所有节点。也许您可以像这样实现Dijkstra算法：在每次迭代中设置一个检查子程序。如果所有所需节点都已固定（已找到最小路径），则终止算法。这将节省其他节点的时间。为了效率，我建议如果不存在负边长度，则使用n次Dijkstra算法。如果有负边长，则使用Johnson算法，它提供了一种特殊的重新加权技术，将负边长转换为非负数。也许您只需要一个更快的服务器。希望这有所帮助。
n/100应被视为Theta(n)，并且你应该使用Floyd-Warshall或类似的算法。如果它相对较小（例如n<=1000），并且n/100被认为是一个常数，则我认为你很难做得比多次使用Dijkstra算法更好...介于两者之间（这相当模糊，我同意），是复杂的部分... - gdelab