Я работаю над алгоритмом Дейкстры, и мне действительно нужно найти все возможные кратчайшие пути, а не только один. Я использую матрицу смежности, и я применил алгоритм Дейкстры, и я могу найти кратчайший путь. Но мне нужно найти все пути с этой минимальной стоимостью, я имею в виду все возможные решения, если они существуют.
Так работает мой алгоритм для одного решения:
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" );
}
