graph - Dijkstra 算法找到所有可能的最短路径

Question

我正在研究 Dijkstra 算法，我真的需要找到所有可能的最短路径，而不仅仅是一条。我正在使用邻接矩阵并应用 Dijkstra 算法，我可以找到最短路径。但是我需要以最低成本找到所有路径，我的意思是所有可能的解决方案，如果它们存在的话。

对于单个解决方案，这就是我的算法的工作方式:

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

如果您在此处以伪代码形式查看 Dijkstra 算法:
Wikipedia Dijkstra's Algorithm Pseudocode

您会注意到被称为“放松”的线。现在它只包含一个情况，如果找到的路径小于当前最短路径，但如果它们相等，则没有任何操作。您可能应该将所有同样短的路径保存在一个列表中。