algorithm - 具有预先计算的最短路径树的 Boosted Dijkstra 算法

Question

最常见的图算法之一是Dijkstra，它以给定节点为根标识加权最短路径树。该算法在使用良好的 Fibonacci 堆实现时，在实际用例中仍然优于理论上应该渐近更好的其他算法，例如Thorup，它的理论复杂度为O(E)，E是图中的边数，因为Thorup 算法中涉及的常数。

在某些情况下，例如，当并行计算通过在 Dijkstra 的并行实例中运行的图的加权直径时，作为图的节点数，必须计算最短路径树。NNN

假设已经计算了一个节点的最短路径树i，现在您想计算相邻节点的最短路径树j。已经计算了以 node 为根的最短路径树i，表示为前任向量或后继向量列表，通过使用树并避免O(log(n))Dijkstra 队列上节点的推送和弹出是否有可能实现加速?

例如，在tenrils 的情况下，两个最短路径树将有很大的重叠：这可以被利用吗？有没有关于这个主题的论文？

随机节点k呢？

标签： algorithmgraphdijkstra