title: Finding all shortest paths and distances using Floyd-Warshall
body: <p>First, a little background: I'm working on building a simple graph class with basic graph algorithms (Dijkstra, Floyd-Warshall, Bellman-Ford, etc) to use as a reference sheet for an upcoming programing competition.</p>
  
  <p>So far I have a functioning version of Floyd-Warshall, but the downside is that so far it's only getting me the shortest <em>distance value</em> between two nodes, not the <em>shortest path</em>.  Preferably I'd like to have the path-building take place within the algorithm itself instead of having to call another function to reconstruct it.</p>
  
  <p>Here's some info on the data structures I'm using:</p>
  
  <p><code>vector&lt; vector&lt;int&gt; &gt; graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF</code></p>
  
  <p><code>vector&lt; vector&lt;int&gt; &gt; path //contains the "stepping stones" on how to reach a given node.  path[st_node][end_node] contains the value of the next node on the way from end_node -&gt; st_node</code></p>
  
  <p>Here's the example graph data I'm using:</p>
  
  <pre><code>INF 10  INF INF INF INF
  INF INF 90  15  INF INF
  INF INF INF INF INF 20
  INF INF INF INF 20  INF
  INF INF  5  INF INF INF
  INF INF INF INF INF INF
  </code></pre>
  
  <p>and here's the desired values to be in the "path" variable (gotten by running Dijkstra from each of the nodes):</p>
  
  <pre><code>INF  0   4   1   3   2
  INF INF  4   1   3   2
  INF INF INF INF INF  2
  INF INF  4  INF  3   2
  INF INF  4  INF INF  2
  INF INF INF INF INF INF
  </code></pre>
  
  <p>Here's a link to the code I'm currently using for the algorithm: <a href="http://pastebin.com/KDY3qHQt" rel="nofollow">(via PasteBin)</a>.</p>
  
  <p>Any help would be greatly appreciated!</p>
  
  <p><em>Edit:</em> I tried <a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction" rel="nofollow">Wikipedia's code</a> to generate the path matrix and here's the result:</p>
  
  <pre><code>INF INF  4   1   3   4
  INF INF  4  INF  3   4
  INF INF INF INF INF INF
  INF INF  4  INF INF  4
  INF INF INF INF INF  2
  INF INF INF INF INF INF
  </code></pre>
  
  <p>It kinda works but has issues when it comes to representing "single" steps.  For example, the path from node 0 to node 1 is undefined everywhere. (But nonetheless, thank you Nali4Freedom for the suggestion)</p>