title: Floyd-Warshall with negative cycles. How do I find all undefined paths?
body: <p>I have implemented the Floyd Warshall algorithm and it works, but the problem is that I don't know how I can find all paths which are not defined. I have searched around the web but I can only find answers to how to detect if a graph has negative cycles or not.</p>
  
  <pre><code>vector&lt; vector &lt;int&gt; &gt; floyd_warshall(vector&lt; vector&lt;int&gt; &gt; d, int n){
      for(int i = 0; i &lt; n; i++) d[i][i] = 0;
  
      for(int i = 0; i &lt; n; i++){
          for(int j = 0; j &lt; n; j++){
              for(int k = 0; k &lt; n; k++){
                  if(d[j][i] + d[i][k] &lt; d[j][k] and d[j][i] != INF and d[i][k] != INF){
                      d[j][k] = d[j][i] + d[i][k];
                  }
              }
          }
      }
  
      return d;
  }
  </code></pre>
  
  <p>After running the algorithm on the graph:</p>
  
  <pre><code>from: to:   weight:
  0     1      1
  1     2     -1
  2     1     -1
  1     3      1
  4     0      1
  </code></pre>
  
  <p>I get the adjacency matrix:</p>
  
  <pre><code>  | 0     1     2     3     4
  --|----------------------------
  0 | 0    -1    -2    -2     INF
  1 | INF  -2    -3    -3     INF
  2 | INF  -3    -4    -4     INF
  3 | INF   INF   INF   0     INF
  4 | 1    -2    -3    -7     0 
  </code></pre>
  
  <p>I know that if node i is part of a negative cycle it has a negative value at position d[i][i] in the matrix. So if I check the diagonal of the matrix I can find all nodes which are part of a negative cycle. So if we look in the example above, we can see that node 1 and 2 are parts of a negative cycle. 
  The thing is that I want to find which paths that are defined and which that are not defined. If you can come from A to B trough a negative cycle then the length of the path should be undefined since it can be arbitrary small. </p>
  
  <p>So the question is, how can i find all undefined paths?</p>
  
  <p>I want the algorithm to return the matrix: (instead of the one above)</p>
  
  <pre><code>  | 0     1     2     3     4
  --|----------------------------
  0 | 0    -INF   -INF    -INF  INF
  1 | INF  -INF   -INF    -INF  INF
  2 | INF  -INF   -INF    -INF  INF
  3 | INF   INF    INF     0    INF
  4 | 1    -INF   -INF    -INF  0 
  </code></pre>
  
  <p>Where d[i][j] = INF means that there is no Path between i and j, and -INF means that there's an arbitrary small path between i and j (the path passes a negative loop somewhere) and otherwise is d[i][j] the shortest length between i and j.</p>
  
  <p>I was thinking of test every single path, but that would probably be too slow. There must be some standard way to solve this problem, right? </p>
  
  <p>Thank you</p>