title: Priority in Queue is behaving wierdly in Dijkstra's algorithm?
body: <p>I implemented Dijkstra's algorithm with priority queue. Everything works perfectly except for this one special instance of the test case and I don't understand how the priority queue is not working. For some background, in my application I turn input in the form of (row, column) into a node and each row and column are nodes bi-directional. The main bug happens when i run this algorithm with an test input and the priority queue pick a node with a distance of 99999 instead of 4! What i mean by this is that when i compare nodes for the priority, they implement a comparable that looks at the distance (between current node and source node). All un-visited nodes are set to 999999(infinity). Therefore, nodes that are visited will be chosen to be the next current node instead of some random node in the graph.</p>
  
  <p>The following code is Dijkstra's algorithm implemented by priority queue.
  <a href="https://github.com/CedricLeong/AlgorithmsProject" rel="nofollow">The project on github.</a></p>
  
  <pre><code>public static void execute(int source){
        PriorityQueue&lt;Vertex&gt; pQueue = new PriorityQueue&lt;Vertex&gt;();
  
          // Set the first node as source node 
          int diameter =0;
          existingVertex.get(source).setDistance(0);
  
          // Add all nodes into a heap
          pQueue.addAll(existingVertex);
              while (!pQueue.isEmpty()){
  
                      // Take out first node
                      Vertex n = pQueue.remove();
                      n.setVisited(true);
                      System.out.println("current node=" + n.id);
  
                      for (Edge e: n.getOutgoingEdges()){
                              Vertex adjNode = e.getDestination();
                              System.out.println("adjNode id=" +adjNode.id);
                              Integer newPossiblePathCost = 1+ n.getDistance();
                              if (Boolean.FALSE.equals(adjNode.isVisited())) {
  
                              if (newPossiblePathCost&lt;adjNode.getDistance()){
                               adjNode.setDistance(newPossiblePathCost); 
                               System.out.println("Distance:" + adjNode.distance);
                                      // update
                               pQueue.remove(adjNode);
                               pQueue.add(adjNode);}}
                      }
  
                      // Save the diameter of the traversed graph
                      if(n.getDistance() &gt; diameter  &amp;&amp; n.getDistance() != 999999)
                      {
                          diameter = n.getDistance();
                      }
              }       
  
              diameterlist.add(diameter);
  
      }
  </code></pre>
  
  <p>Test Case:</p>
  
  <ul>
  1 14
  1 2
  2 15
  3 15
  4 15
  5 15
  6 15
  7 15
  8 15
  9 15
  10 15
  11 15
  12 15
  13 15
  </ul>
  
  <p>Output:</p>
  
  <ol>
  <li>current node=14</li>
  <li>adjNode id=1</li>
  <li>Distance:1</li>
  <li>current node=1</li>
  <li>adjNode id=14</li>
  <li>adjNode id=2</li>
  <li>Distance:2</li>
  <li> current node=2</li>
  <li>adjNode id=1</li>
  <li>adjNode id=15</li>
  <li>Distance:3</li>
  <li><b>current node=13</b></li>
  <li>adjNode id=15</li>
   <li>current node=15</li>
  </ol>
  
  <p>Could anyone explain to me why this happens?</p>