13

Floyd Warshall アルゴリズムを実装しましたが、動作しますが、問題は、定義されていないすべてのパスを見つける方法がわからないことです。Web を検索しましたが、グラフに負のサイクルがあるかどうかを検出する方法しか見つかりません。

vector< vector <int> > floyd_warshall(vector< vector<int> > d, int n){
    for(int i = 0; i < n; i++) d[i][i] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(d[j][i] + d[i][k] < d[j][k] and d[j][i] != INF and d[i][k] != INF){
                    d[j][k] = d[j][i] + d[i][k];
                }
            }
        }
    }

    return d;
}

グラフでアルゴリズムを実行した後:

from: to:   weight:
0     1      1
1     2     -1
2     1     -1
1     3      1
4     0      1

隣接行列を取得します。

  | 0     1     2     3     4
--|----------------------------
0 | 0    -1    -2    -2     INF
1 | INF  -2    -3    -3     INF
2 | INF  -3    -4    -4     INF
3 | INF   INF   INF   0     INF
4 | 1    -2    -3    -7     0

ノード i が負のサイクルの一部である場合、行列の位置 d[i][i] に負の値があることがわかっています。したがって、マトリックスの対角線をチェックすると、負のサイクルの一部であるすべてのノードを見つけることができます。したがって、上記の例を見ると、ノード 1 と 2 が負のサイクルの一部であることがわかります。問題は、定義されているパスと定義されていないパスを見つけたいということです。負のサイクルを介して A から B に到達できる場合、パスの長さは任意に短くなる可能性があるため、未定義にする必要があります。

問題は、未定義のパスをすべて見つけるにはどうすればよいですか?

アルゴリズムが行列を返すようにしたい:(上記の代わりに)

  | 0     1     2     3     4
--|----------------------------
0 | 0    -INF   -INF    -INF  INF
1 | INF  -INF   -INF    -INF  INF
2 | INF  -INF   -INF    -INF  INF
3 | INF   INF    INF     0    INF
4 | 1    -INF   -INF    -INF  0

d[i][j] = INF は i と j の間にパスがないことを意味し、 -INF は i と j の間に任意の小さなパスがあることを意味し (パスはどこかで負のループを通過します)、そうでない場合は d[i ][j] i と j の間の最短の長さ。

パスごとにテストすることを考えていましたが、おそらく遅すぎます。この問題を解決するための標準的な方法があるはずですよね?

ありがとうございました

4

3 に答える 3

12

さて、私は自分の問題の解決策を見つけました。

for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)    // Go through all possible sources and targets

        for(int k = 0; d[i][j] != -INF && k < n; k++)
            if( d[i][k] != INF && // Is there any path from i to k?
                d[k][j] != INF && // Is there any path from k to j?
                d[k][k] < 0)      // Is k part of a negative loop?

                d[i][j] = -INF;   // If all the above are true
                                  // then the path from i to k is undefined

うまくいくはずだと思いますし、うまくいくようです。

于 2013-03-30T17:59:01.667 に答える
0

Floyd-Warshall アルゴリズムは、入力グラフに負のサイクルが存在しない限り、正しい結果を出力します。負のサイクルが存在する場合、最短 (単純) パスの計算は NP 困難な問題であり、Floyd-Warshall アルゴリズムは正しい結果を出力しません。

しかし、行列の対角線に負のエントリがあることを確認することで、負のサイクルの存在を検出することができます。これは、このアルゴリズムの 8 行目と 9 行目で行われます。

1. M[i, j] := ∞ ∀i 6= j
2. M[i, i] := 0 ∀i
3. M[i, j] := c((i, j)) ∀(i, j) ∈ E(G)

4. for i := 1 to n do
5.   for j := 1 to n do
6.     for k := 1 to n do
7.       if M[j, k] > M[j, i] + M[i, k] 
          then M[j, k] := M[j, i] + M[i, k]

8. for i := 1 to n do
9. if M[i, i] < 0 then return(’graph contains a negative cycle’)

ソース

于 2016-03-30T12:21:18.850 に答える