Will multiple solutions for speeding up Dijkstra lower performance?

Question

I have implemented a generic Dijkstra search:

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);
            }
        }
     }
}

Ways for speeding up include:

• Fibonacci heaps
• Bi-directional search

This search will be used as a basis for implementing k-shortest path using Yen's algorithm.

Will applying BOTH speed-ups at the same time on the algorithm improve the search time or will there be some performance loss because both are being used?

Also, are there further speed-ups that can be implemented?

Answer 1

java.util.PriorityQueue.remove is an O(n) operation. If you want to use this PriorityQueue, it is better to permit duplicate vertices in the PriorityQueue, but only process a Vertex the first time it is polled:

class Vertex {
    // existing members

    boolean visited;
}

and

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

While this will increase the size of the priority queue by a factor of up to d (the maximum node degree), and therefore change the runtime to O(dn log(nd)), i.e. O(dn (log n + log d)), this is probabaly acceptable if d is small. In particular, if d is constant (which it is in many real world path finding problems), this algorithm is O(n log n).

Using a pointer based heap implementation such as fibonacci heap would permit to efficiently prevent duplicates in the heap by offering a cost reduction operation, but a pointer based data structure has a poorer constant factor than an array backed priority queue. Moreover, a fibonacci heap is steeper by a constant factor, requiring more nodes to be touched in each operation. Therefore, I suspect it will actually be slower than a binary heap with duplicates (assuming the node is reasonably small).

With bidirectional search, I assume you mean running Dijkstra from both ends in "parallel", until the two meet? This optimization would be independent of improvements in the queue representation, and can well be combined.

Another possible improvement is calling Dijkstra less often, by leveraging the similarity of subsequent Dijkstra invocations by Yen's algorithm. Might it be worthwhile to amend Dijkstra so we could rewind it, rather than start anew from scratch? Alas, I don't quite understand Yen algorithm, so I can not assess whether this would help.

Answer 2

I actually do think that using a Fibonacci heap would be faster, although you may only notice if you call this function many times. Using back tracking as well would also probably help even more.

However, I would recommend that instead of using Yen's algorithm, use the K* algorithm which basically allows you to use A* for the k-shortest path problem! K* has some other benefits as well in particular memory usage for very large graphs.

You can find a free copy of the paper here: (I think there is a newer longer version of this paper as well) K∗: A Directed On-The-Fly Algorithm for Finding the k Shortest Paths

Hope this helps.