Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel