title: Dijkstra algorithm with Adjacency lists
body: <p>So I have been trying to implement the Dijkstra Algorithm for shortest path in a directed graph using adjacency lists, but for I don't know what reason, it doesn't print out the results (prints the minimum distance as 0 to all nodes).</p>
  
  <p>The code I wrote is:
  </p>
  
  <pre><code>#include &lt;fstream&gt;
  #include &lt;functional&gt;
  #include &lt;climits&gt;
  #include &lt;vector&gt;
  #include &lt;queue&gt;
  #include &lt;list&gt;
  
  using namespace std;
  
  struct node {
      int vertex;
      int weight;
      node(int v, int w) : vertex(v), weight(w) { };
      node() { }
  };
  
  class CompareGreater {
      public:
          bool const operator()(node &amp;nodeX, node &amp;nodeY) {
              return (nodeX.weight &gt; nodeY.weight) ;
          }
  };
  
  vector&lt; list&lt;node&gt; &gt; adj;
  vector&lt;int&gt; weights;
  priority_queue&lt;node, vector&lt;node&gt;, CompareGreater&gt; Q;
  
  int nrVertices, nrEdges;
  
  void readData();
  void Dijkstra(node);
  void writeData();
  
  int main(int argc, char *argv[]) {
  
      readData();
      Dijkstra(node(1, 0));
      writeData();
  
      return 0;
  }
  
  void readData() {
      fstream in("dijkstra.in", ios::in);
  
      int nodeX, nodeY, weight;
  
      in &gt;&gt; nrVertices &gt;&gt; nrEdges;
  
      adj.resize(nrVertices+1);
      weights.resize(nrVertices+1);
  
      for (int i = 1; i &lt;= nrVertices; ++i) {
          weights.push_back(INT_MAX);
      }
  
      for (int i = 1; i &lt;= nrEdges; ++i) {
          in &gt;&gt; nodeX &gt;&gt; nodeY &gt;&gt; weight;
          adj[nodeX].push_back(node(nodeY, weight));
      }
  
      in.close();
  }
  
  void Dijkstra(node startNode) {
      node currentNode;
  
      weights[startNode.vertex] = 0;
      Q.push(startNode);
  
      while (!Q.empty()) {
          currentNode = Q.top();
          Q.pop();
  
          if (currentNode.weight &lt;= weights[currentNode.vertex]) {
              for (list&lt;node&gt;::iterator it = adj[currentNode.vertex].begin(); it != adj[currentNode.vertex].end(); ++it) {
                  if (weights[it-&gt;vertex] &gt; weights[currentNode.vertex] + it-&gt;weight) {
                      weights[it-&gt;vertex] = weights[currentNode.vertex] + it-&gt;weight;
                      Q.push(node((it-&gt;vertex), weights[it-&gt;vertex]));
                  }
              }
          }
      }
  }
  
  void writeData() {
      fstream out("dijkstra.out", ios::out);
  
      weights.resize(nrVertices+1);
      for (vector&lt;int&gt;::iterator it = weights.begin()+1; it != weights.end(); ++it) {
          out &lt;&lt; (*it) &lt;&lt; " ";
      }
  
      out.close();
  }
  </code></pre>
  
  <p>The input data was:</p>
  
  <pre><code>5 7
  1 2 10
  1 3 2
  1 5 100
  2 4 3
  3 2 5
  4 3 15
  4 5 5
  </code></pre>
  
  <p>It means there are 5 nodes, 7 arcs (directed edges), and the arcs exist from node 1 to 2 with the cost of 10, from 1 to 3 with the cost of 2, and so on.</p>
  
  <p>However, the output is wrong. I have no idea where the program might fail. I took the main idea from here: <a href="http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=standardTemplateLibrary2#dijkstra1" rel="nofollow">http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=standardTemplateLibrary2#dijkstra1</a>
  (At the end it gives the idea for Dijkstra's Algorithm using a priority_queue).</p>
  
  <p>Thanks in advance.</p>
  
  <p><em><strong>Raul</em></strong></p>