title: Why is the Java Priority Queue not empty after execution in the following code?
body: <p>I am trying to implement Dijkstra Algorithm and have used the following code. I have used the debugger in Eclipse to step through the program and have found that it produces correct values mid way through the execution. However after that, the priority queue that I have used from the java.util package, does not show up to be empty. While theoretically it should be empty from the following code.</p>
  
  <p>From the debugger, it can be seen that the priority queue contains references with values set to Infinity. What is the bug in the code?</p>
  
  <pre><code>import java.util.Arrays;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.PriorityQueue;
  
  
  public class Dijkstra {
      static class Vertex implements Comparable&lt;Vertex&gt;{
          private int vertexid;
          private Double distance;
  
          public Vertex(int vertexid, Double distance) {
              this.vertexid = vertexid;
              this.distance = distance;
          }
  
          public int getVertexid() {
              return vertexid;
          }
  
          public Double getDistance() {
              return distance;
          }
  
          public int compareTo(Vertex other) {
              return this.getDistance().compareTo(other.getDistance());
          }
  
          public boolean equals(Object o) {
              if (o instanceof Vertex) {
                  Vertex v = (Vertex) o;
                  return vertexid == v.vertexid &amp;&amp; distance == v.distance;
              }
              return false;
          }
      }
  
      public static void dijkstra(double g[][], int n, int m, int source) {
          // g is the adjacency matrix
          // n is the number of nodes
          // m is the number of edges
  
          // initialize shortest path
  
          double d[] = new double[n];
  
  
          for (int i = 0; i &lt; n; i++) {
              d[i] = Double.POSITIVE_INFINITY;
          }
          d[source] = 0;
  
          HashMap&lt;Integer, Double&gt; s = new HashMap&lt;Integer, Double&gt;();
          PriorityQueue&lt;Vertex&gt; q = new PriorityQueue&lt;Vertex&gt;();
  
          // initialize q
          for (int i = 0; i &lt; n; i++) {
              q.add(new Vertex(i, d[i]));
          }
  
          Vertex u;
  
          while (!q.isEmpty()) {
              u = q.remove();
              //System.out.println(u.getVertexid() + "\t" + u.getDistance());
              s.put(u.getVertexid(), u.getDistance());
  
              for (int i = 0; i &lt; n; i++) {
                  if (i != u.getVertexid() || g[u.getVertexid()][i] != Double.POSITIVE_INFINITY) {
                      if (u.getDistance().doubleValue() + g[u.getVertexid()][i] &lt; d[i] &amp;&amp; s.containsKey(i) == false) {
                          q.remove(new Vertex(i, d[i]));
                          d[i] = u.getDistance().doubleValue() + g[u.getVertexid()][i];
                          q.add(new Vertex(i, d[i]));
                      }
                  }
              }
          }
  
          /*for(double i: d){
              System.out.println(i);
          }*/
  
          System.out.println(Arrays.asList(s));
      }
  
      public static void main(String[] args) {
          double graph[][] = {{Double.POSITIVE_INFINITY, 4, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 8, Double.POSITIVE_INFINITY},
                  {4, Double.POSITIVE_INFINITY, 8, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 11, Double.POSITIVE_INFINITY},
                  {Double.POSITIVE_INFINITY, 8, Double.POSITIVE_INFINITY, 7, Double.POSITIVE_INFINITY, 4, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2},
                  {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 7, Double.POSITIVE_INFINITY, 9, 14, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
                  {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 9, Double.POSITIVE_INFINITY, 10, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
                  {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 4, 14, 10, Double.POSITIVE_INFINITY, 2, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
                  {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2, Double.POSITIVE_INFINITY, 1, 6},
                  {8, 11, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 1, Double.POSITIVE_INFINITY, 7},
                  {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 6, 7, Double.POSITIVE_INFINITY}
                 };
  
          Dijkstra.dijkstra(graph, 9, 14, 0);
  
      }
  }
  </code></pre>
  
  <p>The following are the references from the debugger:</p>
  
  <p><a href="https://i.stack.imgur.com/btkdn.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/btkdn.png" alt="enter image description here"></a></p>
  
  <p>And for the Priority Queue Contents:</p>
  
  <p><a href="https://i.stack.imgur.com/Gb5tl.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Gb5tl.png" alt="enter image description here"></a></p>
  
  <p>After the execution the s values all get set to infinity.</p>