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

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[] adj) {
    HashSet 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[] adj) {
PriorityQueue 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]));
}

wh

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

StackExchange Code Review Q#150685, answer score: 3