我正在研究 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" );
}