title: Dijkstra's algorithm to find all the shortest paths possible
body: <p>I'm working on Dijkstra's algorithm, and I really need to find all the possible shortest paths, not just one. I'm using an adjacency matrix and I applied Dijkstra's algorithm, and I can find the shortest path. But I need to find all the paths with that minimum cost, I mean all the possible solutions, if they exist.</p>
  
  <p>This is how my algorithm works, for a single solution:</p>
  
  <pre><code>public void dijkstra( int graph[][] )
  {
      int d[] = new int[ graph.length ];
      int dC[] = new int[ graph.length ];
      int p[] = new int[ graph.length ];
  
      for( int i = 0; i &lt; graph.length; i++ ){
          d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1;
      }
      d[ 0 ] = 0; dC[ 0 ] = 0;
  
      int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
      while( i &lt; graph.length ){
          //extract minimum
          for( int j = 0; j &lt; dC.length; j++ ){
              if( min &gt; d[ j ] &amp;&amp; dC[ j ] != -1 ){
                  min = d[ j ]; pos = j;
              }
          }
          dC[ pos ] = -1;
  
          //relax
          for( int j = 0; j &lt; graph.length; j++ ){
              if( d[ j ] &gt; graph[ pos ][ j ] + d[ pos ] ){
                  d[ j ] = graph[ pos ][ j ] + d[ pos ];
                  p[ j ] = pos;
              }
          }
          i++; min = 200;
      }
  
      for( int j = 0; j &lt; p.length; j++ ){
          System.out.print( p[ j ] + " " );
      }
      System.out.print( "\n" );
      for( int j = 0; j &lt; d.length; j++ ){
          System.out.print( d[ j ] + " " );
      }
      System.out.print( "\n" );
  }
  </code></pre>