2

私のアルゴリズム（floyd-warshall）が最短経路を計算するときに渡された頂点をリストダウンする方法を理解できないようです。再帰を使用する必要があると言われましたが、再帰の使用方法がわかりません。疑似コード/例を教えてください。大歓迎です!

    import java.util.*;
    public class Main{
        public static final int INF = 9999999;
        public static int[][] path;
        public static int[] tax;
        public static void main(String[] adsf){
            Scanner pp = new Scanner(System.in);
            int testCases = pp.nextInt();
            pp.nextLine();
            pp.nextLine();
            while(testCases-- >0){
                String[] s1 = pp.nextLine().split(" ");
                int size = s1.length;
                path = new int[size][size];
                for(int i = 0; i < path.length; i++)
                    Arrays.fill(path[i],INF);
                tax = new int[size];
                for(int j = 0; j < path[0].length; j++){
                    path[0][j] = Integer.parseInt(s1[j]);
                    if(path[0][j]==-1)path[0][j]=INF;
                }
                for(int i = 1; i < path.length;i++){
                    s1 = pp.nextLine().split(" ");
                    for(int j = 0; j < path[0].length; j++){
                        path[i][j] = Integer.parseInt(s1[j]);
                        if(path[i][j]==-1)path[i][j]=INF;
                    }
                }
                for(int k=0; k<tax.length;k++){
                    tax[k] = pp.nextInt();
                } pp.nextLine();    
                sssp();
                }
                int x,y;
                while(pp.hasNextInt()){
                    x=pp.nextInt();
                    y=pp.nextInt();
                    int cost = path[x-1][y-1];
                    System.out.println((x-1)+" "+(y-1)+" "+cost);
                }
            }
        }
        public static void sssp(){
            for(int k=0;k<path.length;k++){
                for(int i=0;i<path.length;i++){
                    for(int j=0;j<path.length;j++){
                        path[i][j] = Math.min(path[i][j],path[i][k]+path[k][j]);
                    }
                }   
            }
        }
    }
4

1 に答える 1

1

パスの再構築に再帰を使用する必要はありません (実際、 Java では再帰を使用する必要はありません。これを含む特定の問題を解決するために再帰を使用する方がはるかに便利です)。

長さに加えて最短パスを計算できるようにするには、ノードの後続ノードをパスに格納する 2 番目の 2D 配列が必要です。この記事を見てください。私が話している配列はnext、疑似コードで呼び出されます。

アルゴリズムのロジックは次のようになることを思い出してください。「以前に発見されたパスを経由するよりも速くからiをj経由できる場合は、そのパスを現在の最短パスとして使用します」。あとは、次のように、通過する決定を他の配列に格納するだけです。kijkk

if (path[i][k] + path[k][j] < path[i][j]) {
    path[i][j] = path[i][k]+path[k][j];
    next[i][j] = k;
}

Floyd-Warshal が終了したら、最初に からiへのパスを再構築し、次に からへのパスを再構築することで、 からへのパスを再構築できます。jikkj

String GetPath (int i, int j) {
    if (path[i][j] == INF) return "no path";
    int intermediate = next[i][j];
    if (intermediate < 0) return " ";
    return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);
}
于 2012-05-17T15:36:03.790 に答える