Databases
StackOverflow2013
Postsdbo
POFloyd Warshall algorithm using adjacency list
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFloyd Warshall algorithm using adjacency list
    text
    copied!<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>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload