Dijkstra's algorithm using priority queue running slower than without PQ
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 &lt; 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 &lt; 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 &lt; adj.length; i++) {
        if (i != source) {
            dist[i] = Integer.MAX_VALUE;
            prev[i] = Integer.MAX_VALUE;
        }

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




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

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