title: Floyd Warshall algorithm using adjacency list
body: <p>I had implemented the Floyd Warshall algorithm using adjacency matrix in C++ as given below, but I used the adjacency matrix representation which made it very convenient to loop over the (i,j,k) indices. Is there a way to accomplish this in adjacency list represtation? I saw that even <a href="http://mcs.uwsuper.edu/sb/425/Prog/FloydWarshall.java" rel="nofollow">http://mcs.uwsuper.edu/sb/425/Prog/FloydWarshall.java</a> this site converts adjacency list into matrix before applying the algorithm.</p>
  
  <pre><code>int rowSize = numberOfGraphVertices,  colSize = numberOfGraphVertices ;
      std::vector&lt;int&gt; shortestPathMatrix(rowSize * colSize, 10000000);
  
      for (int i = 0; i &lt; rowSize; ++i) shortestPathMatrix[i + i * colSize] = 0 ;
      cout &lt;&lt; "Done" &lt;&lt; endl ; 
      int numEdges = 0;
      while(getline(infile, graphString)) // To get you all the lines.
      {
  
           pch = strtok_s(const_cast&lt;char *&gt; (graphString.c_str())," ", &amp;p2);
           int rowNumber = atoi(pch);
          //graphListVector[node1] = 
           pch = strtok_s(NULL, " ", &amp;p2);
           int colNumber = atoi(pch);
           pch = strtok_s(NULL, " ", &amp;p2);
           int edgeWeight = atoi(pch);
           shortestPathMatrix[(rowNumber-1)*colSize + (colNumber-1)] = edgeWeight;
           ++numEdges;
      }
      cout&lt;&lt; "numberOfVertices"&lt;&lt;numberOfGraphVertices&lt;&lt;"NumberOfEdges"&lt;&lt; numEdges &lt;&lt;endl;
      t = clock();
      //for (int i = 0 ; i &lt; 1002 ; ++i) cout &lt;&lt; "Value" &lt;&lt; i &lt;&lt;" " &lt;&lt; shortestPathMatrix[i] &lt;&lt; endl; 
      for (int k = 0 ; k &lt; rowSize ; ++k){
          for (int i = 0 ; i &lt; rowSize ; ++i){
              for (int j = 0; j &lt; rowSize ; ++j){
                  if ( shortestPathMatrix[j*colSize + i] + shortestPathMatrix[i*colSize + k] &lt; shortestPathMatrix[j*colSize + k])
                      shortestPathMatrix[j*colSize + k] = shortestPathMatrix[j*colSize + i] + shortestPathMatrix[i*colSize + k];
              }
          }
      }
      for (int i = 0; i &lt; rowSize; ++i) {
          if (shortestPathMatrix[i + i * colSize] &lt; 0) cout &lt;&lt; "Negative cycle found" &lt;&lt; endl;
          break;
      }
       std::vector&lt;int&gt;::iterator minShortestPathIndex = std::min_element (shortestPathMatrix.begin(), shortestPathMatrix.end());
  </code></pre>