这就是我的算法的工作方式，对于单个解决方案：
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如果你看看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( "\n" ); for( int j = 0; j < d.length; j++ ){ System.out.print( d[ j ] + " " ); } System.out.print( "\n" ); }解决方案
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的算法找到所有可能的最短路径
发布评论