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的算法: 维基百科Dijkstra的算法伪代码

你会注意到被称为放松的线.现在它只包含一个案例,如果找到的路径小于当前最短路径,但如果它们相等则没有任何事情.您应该在列表中保留所有相同的短路径.

Answer 2

如果您的 Dijkstra 算法的实现基于优先级队列，请采用您的第一个解决方案，记录深度并不断弹出解决方案，直到距离发生变化。