Dijkstra's algorithm using priority queue running slower than without PQ

Question

I need to implement dijkstra's algorithm and I've done so using this Wikipedia page. I've done it both with priority queue and without.

Both versions work 100% correct, however I need the faster one (priority queue one). The problem is that it isn't faster. My tests show "faster" one runs in more than double the time that "slower" one does, it shouldn't do that. What am I doing wrong?

//more primitive version that in fact runs faster (it shouldn't)

//source is starting node, adj adjacency list, Road represents one edge
private static int dijkstra (int source, ArrayList<Road>[] adj) {
    HashSet<Integer> vertices = new HashSet<>();

    int[] dist = new int[adj.length];
    int[] prev = new int[adj.length];

    for (int i = 0; i < adj.length; i++) {
        dist[i] = Integer.MAX_VALUE;
        prev[i] = Integer.MAX_VALUE;
        vertices.add(i);
    }

    dist[source] = 0;

    while (!vertices.isEmpty()) {
        int currentPathLen = Integer.MAX_VALUE, current = -1;
        for (int v: vertices) {
            if (dist[v] < currentPathLen) {
                current = v;
                currentPathLen = dist[current];
            }
        }

        vertices.remove(current);

        for (Road v: adj[current]) {
            int alt = dist[current] + v.distance;

            if (alt < dist[v.end]) {
                dist[v.end] = alt;
                prev[v.end] = current;
            }
        }
    }
}

---

//this one should run faster

//same variables as primitive version, except for Node, 
//which is made only for PQ prioritizing
private static int improvedDijkstra(int source, ArrayList<Road>[] adj) {
    PriorityQueue<Node> vertices = new PriorityQueue<>();

    int[] dist = new int[adj.length];
    int[] prev = new int[adj.length];

    dist[source] = 0;

    for (int i = 0; i < adj.length; i++) {
        if (i != source) {
            dist[i] = Integer.MAX_VALUE;
            prev[i] = Integer.MAX_VALUE;
        }

        vertices.add(new Node(i, dist[i]));
    }

    while (!vertices.isEmpty()) { //O(n)
        Node u = vertices.poll(); //this should have O(logn)

        for(Road v: adj[u.value]) {  // I suspect the problem is this loop, but it is same 
                                     // as in Wikipedia page

            int alt = dist[u.value] + v.distance;

            if (alt < dist[v.end]) {
                dist[v.end] = alt;
                prev[v.end] = alt;

                vertices.add(new Node(v.end, alt)); //this should have O(logn)
            }
        }
    }

Answer 1

I think the problem is that you have more than one instance of a node in the priority queue at a given time.

In the relax operation:

 if (alt < dist[v.end]) {
     dist[v.end] = alt;
     prev[v.end] = alt;

     vertices.add(new Node(v.end, alt)); //this should have O(logn)
 }

You should remove the vertex before adding it or implement a indexed priority queue with a decreased key operation like this one. I'm not sure if java remove operation is \$O(ln(n))\$ thought. Like this:

if (alt < dist[v.end]) {
     dist[v.end] = alt;
     prev[v.end] = alt;
     Node newNode = new Node(v.end, alt);
     vertices.remove(newNode);
     vertices.add(newNode);
 }

Note: You need to override equals for the node.

With the indexed priority queue you would create and add the new node if the queue doesn't contains it, or do decreased key otherwise.

---

If you do it like this you will lazily add each vertex to the queue so you don't need to add them all at the beginning here:

   dist[source] = 0;
   for (int i = 0; i < adj.length; i++) {
        if (i != source) {
            dist[i] = Integer.MAX_VALUE;
            prev[i] = Integer.MAX_VALUE;
        }

        vertices.add(new Node(i, dist[i])); // <--here
    }

---

Also you can remove the inner if in the loop like this:

   for (int i = 0; i < adj.length; i++) {         
       dist[i] = Integer.MAX_VALUE;
       prev[i] = Integer.MAX_VALUE;
    }
    dist[source] = 0;
    vertices.add(new Node(source, 0));

Answer 2

Do not visit a node twice

Your function needs to track whether a vertex has been visited before, and prevent it from being visited twice. In the wikipedia article, that requirement is mentioned in a comment here:

     for each neighbor v of u:       // only v that is still in Q

Another difference is that the wikipedia article assumes that the pq (priority queue) has a "decrease priority" function:

     Q.decrease_priority(v, alt)

What this means is that if the pq already contains a particular vertex, the "decrease priority" function will move that vertex within the pq by decreasing its value. For example, if vertex 1 has cost 10, and then you want to decrease its cost to 3, the decrease priority function will move/reinsert the vertex into the correct place in the pq.

If you don't have a decrease priority function, you can just add multiple copies of the same vertex into the pq (which is what you are doing). For example, you can insert "vertex 1 cost 10" into the pq, and later insert "vertex 1 cost 3" into the pq, knowing that the cost 3 node will be pulled out of the pq first. The problem is that later on, you will pull "vertex 1 cost 10" out of the pq. But if you tracked the visited vertices, you will be able to ignore this "out of date" pq node.

Starting set

You prepopulate your priority queue with every vertex, with each vertex having infinite distance except for the source vertex, which has 0 distance. Actually, you only need to prepopulate your priority queue with the source vertex. If any of the other vertices are reachable, they will eventually be added to the priority queue.

Sample modifications

Here is your code with modifications mentioned above:

private static int improvedDijkstra(int source, ArrayList<Road>[] adj) {
    PriorityQueue<Node> vertices = new PriorityQueue<>();

    int [] dist    = new int [adj.length];
    int [] prev    = new int [adj.length];
    bool[] visited = new bool[adj.length];

    dist[source] = 0;

    for (int i = 0; i < adj.length; i++) {
        if (i != source) {
            dist[i] = Integer.MAX_VALUE;
            prev[i] = Integer.MAX_VALUE;
        }
    }

    // Start with source node only.
    vertices.add(new Node(source, 0));

    while (!vertices.isEmpty()) { //O(n)
        Node u = vertices.poll(); //this should have O(logn)

        if (visited[u.value])
            continue;
        visited[u.value] = true;

        for(Road v: adj[u.value]) {
            // No need to connect to vertices already visited.
            if (visited[v.end])
                continue;

            int alt = dist[u.value] + v.distance;

            if (alt < dist[v.end]) {
                dist[v.end] = alt;
                prev[v.end] = alt;

                vertices.add(new Node(v.end, alt)); //this should have O(logn)
            }
        }
    }
}

Answer 3

Do you really need it to be Dijkstra's Algorithm? Because there is an adaption to Dijkstra's algorithm available called A*. It is very similar to Dijkstra, except it uses an additional heuristic to greatly speed it up.

Here is a great article about the algorithm: https://www.raywenderlich.com/4946/introduction-to-a-pathfinding