1

次の論文の4ページにあるアルゴリズムを使用して、すべてのペアの最短経路行列を計算しようとしています。

http://www.waset.org/journals/ijcms/v3/v3-5-43.pdf

（アルゴリズムの）7行目と8行目、続いて11行目と12行目で混乱しています。これは、s1にjの値を割り当て、両方を使用すると、8行目の比較があいまいに見えるためです。インデントを間違って読んでいるのではないかと思います。私はアルゴリズムに不慣れなので、しばらくお待ちください。

    while(flag != false){
        for(int i=0; i<n;i++){
            aMin = Integer.MAX_VALUE;
            bMin = Integer.MAX_VALUE;

            for(int j=0; j<n;j++){
                // Line 7 of the algorithm
                if((distanceMatrix[i][j] < aMin) && (j != i) && (BR[i][j] == false)){
                    aMin = distanceMatrix[i][j];
                    BR[i][j] = true;
                    a[i] = j;
                    int s1 = j; // End of line 7
                    // Line 8 of the algorithm
                    if(distanceMatrix[i][j] < distanceMatrix[i][s1])
                        BR[i][s1] = false; // End of line 8
                }

            }

            for(int j=0; j<n; j++){
                // Line 11 of the algorithm
                if((distanceMatrix[i][j] < bMin) && (j != i) && (j != a[i]) && (BR[i][j] == false)){
                    bMin = distanceMatrix[i][j];
                    BR[i][j] = true;
                    b[i] = j;
                    int s2 = j; // end of line 11

                    // Line 12 of the algorithm
                    if(distanceMatrix[i][j] < distanceMatrix[i][s2])
                        BR[i][s2] = false; // end of line 12
                }
            }
        }

        for(int i=0; i <n; i++){
            for(int j=0; j<n; j++){
                int t1 = distanceMatrix[i][a[i]] + distanceMatrix[a[i]][j];
                int t2 = distanceMatrix[i][b[i]] + distanceMatrix[b[i]][j];
                distanceMatrix[i][j] = Math.min(distanceMatrix[i][j], Math.min(t1,t2));
                distanceMatrix[j][i] = distanceMatrix[i][j];
            }
        }

        flag = true;
        for(int i=0; i<n;i++){
            // Line 19 of the algorithm
            for(int j=0; j<n; j++){
                temp[i][j] = distanceMatrix[i][j]; // end of line 19
                // Line 20 of the algorithm
                if (distanceMatrix[i][j] == temp[i][j])
                    flag  = false; // end of line 20
            }
        }
    }

さらに、アルゴリズムの19行目と20行目を見ると、フラグが常にtrueであるため、ループでスタックすることがわかります。

4

1 に答える 1

1

私はそれがこのようになるべきだと思います：

4) for i ← 1 to n do amin← ∞ ; bmin ← ∞
5)   for j ← 1 to n do
6)     if D[i, j] < amin and j = i and BR[i, j] = 0 then
7)       amin ← D[i, j] ; BR[i, j] ← 1 ; a[i] ← j ; s1 ← j
8)     if D[i, j] < D[i, s1] then BR[i, s1] ← 0

ご覧のとおり、常にそうであるとは限りません。ただし、常にそうなるでしょs1う。j<= j

したがって、2番目ifは最初の内部にはありません。そうでなければ、それは意味がありません。なぜなら、s1 == j常にそしてあなたは持つことができないからD[i, j] < D[i, j]です。

于 2012-06-29T14:25:12.173 に答える