title: Which datatype to use as queue in Dijkstra's algorithm?
body: <p>I'm trying to implement Dijkstra's algorithm in Java (self-study). I use the pseudo-code provided by Wikipedia (<a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode">link</a>). Now near the end of the algorithm, I should <code>decrease-key v in Q;</code>. I guess i should have implemented Q with a BinaryHeap or something like that? What would be the right (built-in) datatype to use here?</p>
  
  <pre><code>private void dijkstra(int source) {
          int[] dist = new int[this.adjacencyMatrix.length];
          int[] previous = new int[this.adjacencyMatrix.length];
          Queue&lt;Integer&gt; q = new LinkedList&lt;Integer&gt;();
  
          for (int i = 0; i &lt; this.adjacencyMatrix.length; i++) {
              dist[i] = this.INFINITY;
              previous[i] = this.UNDEFINED;
              q.add(i);
          }
  
          dist[source] = 0;
  
          while(!q.isEmpty()) {
              // get node with smallest dist;
              int u = 0;
              for(int i = 0; i &lt; this.adjacencyMatrix.length; i++) {
                  if(dist[i] &lt; dist[u])
                      u = i;
              }
  
              // break if dist == INFINITY
              if(dist[u] == this.INFINITY) break;
  
              // remove u from q
              q.remove(u);
  
              for(int i = 0; i &lt; this.adjacencyMatrix.length; i++) {
                  if(this.adjacencyMatrix[u][i] == 1) {
                      // in a unweighted graph, this.adjacencyMatrix[u][i] always == 1;
                      int alt = dist[u] + this.adjacencyMatrix[u][i]; 
                      if(alt &lt; dist[i]) {
                          dist[i] = alt;
                          previous[i] = u;
  
                          // here's where I should "decrease the key"
                      }
                  }
              }
          }
      }
  </code></pre>