Dijkstra's algorithm to find all the shortest paths possible

Question

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.

This is how my algorithm works, for a single solution:

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 < 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 < graph.length ){
        //extract minimum
        for( int j = 0; j < dC.length; j++ ){
            if( min > d[ j ] && dC[ j ] != -1 ){
                min = d[ j ]; pos = j;
            }
        }
        dC[ pos ] = -1;

        //relax
        for( int j = 0; j < graph.length; j++ ){
            if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                d[ j ] = graph[ pos ][ j ] + d[ pos ];
                p[ j ] = pos;
            }
        }
        i++; min = 200;
    }

    for( int j = 0; j < p.length; j++ ){
        System.out.print( p[ j ] + " " );
    }
    System.out.print( "\n" );
    for( int j = 0; j < d.length; j++ ){
        System.out.print( d[ j ] + " " );
    }
    System.out.print( "\n" );
}

Answer 1

If you look at Dijkstra's algorithm in pseudocode form here: Wikipedia Dijkstra's Algorithm Pseudocode

You will notice the line referred to as a Relax. Right now it only contains a case for if the path found is less than the current shortest path, but there isn't anything done if they are equal. You should probably keep all the equally short paths in a List.

Answer 2

If your implementation of Dijkstra's algorithm is based on a priority queue, take your first solution, record the depth and keep popping solutions out until the distance changes.