algorithm - 有没有一种有效的方法可以在函数图中找到最短路径？

Question

我的任务是处理Q具有 V 的函数图中的最短路径查询节点。 Q和 V是可以达到 100000 的整数.
我的第一个想法是使用 Floyd-Warshall 算法来有效地回答查询，但是这个算法需要 O(V^3)计算最短路径的时间太慢了。
我的第二个想法运行在 O(QV)时间，因为对于每个查询，我从起始节点开始并遍历图直到我发现一个循环或到达目标节点。
但是，这个解决方案还是太慢了；当 V 时，它没有机会快速处理查询和 Q变大。我认为有一些预处理或其他技术可以用来解决这个问题，但我一直无法找到任何在线资源来帮助指导我。有人可以帮我吗？

Answer 1

函数图意味着每个节点只有一个出边，因此 A 和 B 之间的最大步数不能超过不遇到循环的顶点数。你应该是O(V)。
由于没有选择，您可以轻松构建一个 CostMap[V][V] 记录两个节点之间的距离，并在遇到查询时懒惰地填充它；因此连续查询将接近恒定时间。