如何改进对同一个图的多个最短路径搜索？

Question

我遇到了下一个情况，我需要找到解决问题的最佳优化方法。

我图G

举个例子让我们假设图表看起来像这样

而这个问题需要找到几个顶点之间的最短路径（我们称之为SP）中的权重相加并将它们全部相加。

我的意思是如果 a - b 之间的最短路径是 a -> c -> d 他的 SP 将是 x0 + x1 + x2

所以我的一组问题看起来像这样：

• a - g
• a - h
• e - f
• .....等等

所以天真的解决方案是每次都在每个集合之间找到 SP

SP(a,g) + SP(a,h) + SP(e,f) + ... = result

所以这是优化任务开始的时候，我已经实施了两项改进，但我需要最好的优化（如果可能的话），让我们看看我已经做了什么：

1. 保存找到的每条最短路径的每个结果，这样如果再次询问我就有问题了

例子。如果 a - g 之间的 SP 是 w 我保存它所以如果我再次询问 a - g 或 g - a 之间的 SP 的值是哪个我已经知道结果了

2. 保存每个后续 SP 找到并保存它

示例。

如果我要求在 a - g 之间找到 SP。让我们假设这两个顶点之间的最短路径是 a -> c -> d -> j -> g 所以 SP 将是

x0 + x1 + x2 + x3

所以我可以保存 a - g 但我也可以保存找到的所有后续路径的 SP。

例如 a 和 j 之间的最短路径是 a -> c -> d -> j 或者 c and j 之间的路径是 c -> d -> j

这是所有 SP 的发现

SP(a,c) = x0
SP(a,d) = x0 + x1
SP(a,j) = x0 + + x1 + x2

SP(c,d) = x1
SP(c,j) = x1 + x2
SP(c,g) = x1 + x2 + x3

SP(d,j) = x2
SP(d,g) = x2 + x3

SP(j,g) = x3

我会保存每一个结果。

所以现在这最后的改进已经节省了很多时间，但是似乎还不够，因为要找到的节点和SP的集合相当大。

所以我可以用来改善这个问题的任何建议或任何特定算法（我希望已经足够清楚，如果有任何细节没有解释，请写评论）？

Answer 1

您可以使用Dijustra搜索一个节点与所有其他节点之间的最短路径，并使用哈希缓存所有最短路径的长度table。

然后，对于给定的一组节点对，您可以从哈希中快速提取路径长度table。

Answer 2

如果要计算很多对，请考虑Floyd-Warshall；它将为您提供从任何点到任何其他点的最短路径距离（以 O(n^3) 运行时间为代价）。