java - 加速 Dijkstra 的多种解决方案会降低性能吗？

Question

我已经实现了一个通用的 Dijkstra 搜索:

public void search(Vertex source) {
    source.minDistance = 0;

    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex u = vertexQueue.poll();

        for (Edge e : u.edges) {
            Vertex v = e.target;

            int weight = e.weight;
            int distance = u.minDistance + weight;

            if (distance < v.minDistance) {
                vertexQueue.remove(v);

                v.minDistance = distance ;
                v.previous = u;

                vertexQueue.add(v);
            }
        }
     }
}

加速的方法包括:

• 斐波那契堆
• 双向搜索

此搜索将用作使用 Yen 算法实现 k 最短路径的基础。

在算法上同时应用两种加速是否会缩短搜索时间，还是会因为同时使用两种加速而导致一些性能损失？

此外，是否可以进一步提高速度？

Answer 1

java.util.PriorityQueue.remove 是一个 O(n) 操作。如果要使用此 PriorityQueue，最好允许 PriorityQueue 中有重复的顶点，但只在第一次轮询时处理 Vertex:

class Vertex {
    // existing members

    boolean visited;
}

和

        Vertex u = vertexQueue.poll();
        if (u.visited) continue;
        u.visited = true;

虽然这会将优先级队列的大小增加到 d(最大节点度)，因此将运行时间更改为 O(dn log(nd))，即 O(dn (log n + log d))，如果 d 很小，这可能是可以接受的。特别是，如果 d 是常数(在许多现实世界的寻路问题中都是如此)，则此算法为 O(n log n)。

使用基于指针的堆实现(例如斐波那契堆)可以通过提供成本降低操作来有效地防止堆中的重复项，但是基于指针的数据结构具有比数组支持的优先级队列更差的常量因子。此外，斐波那契堆的陡峭度为常数倍，每次操作需要接触更多的节点。因此，我怀疑它实际上会比具有重复项的二进制堆慢(假设节点相当小)。

对于双向搜索，我假设您的意思是从两端“并行”运行 Dijkstra，直到两者相遇？这种优化将独立于队列表示的改进，并且可以很好地结合起来。

另一个可能的改进是通过利用 Yen 算法后续 Dijkstra 调用的相似性，减少调用 Dijkstra 的次数。是否值得修改 Dijkstra，以便我们可以倒带它，而不是从头开始？ las，我不太了解日元算法，所以我无法评估这是否有帮助。