Dijkstra 算法找到所有可能的最短路径 [英] Dijkstra's algorithm to find all the shortest paths possible

问题描述

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

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( "
" );
    for( int j = 0; j < d.length; j++ ){
        System.out.print( d[ j ] + " " );
    }
    System.out.print( "
" );
}

推荐答案

如果您在此处以伪代码形式查看 Dijkstra 算法:维基百科 Dijkstra 的算法伪代码

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.

这篇关于Dijkstra 算法找到所有可能的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！