1

Floyd-Warshalls アルゴリズムを使用したグラフ検索に取り組んでいますが、負のループを防ぐためにそれを変更する方法がわかりません。

私が入るとき：

From  Cost   To
0      -1     1
1      -2     0

コストマトリックスを取得します：

   0   1
0 -3  -4
1 -5 -10

その後、負のエッジを追加してコストをさらに削減するため、クラッシュするまでループを開始します。

void FloydWarshall(int ***distanceMatrix, int maxVertices)
{
int from, to, via;

for(from = 0; from < maxVertices; from++)
{
 for(to = 0; to < maxVertices; to++)
 {
      for(via = 0; via < maxVertices; via++)
       {
         //Fix the negative looping
         //EDIT FIX:
         if((*distanceMatrix)[via][via]<0)
         {fprintf(stderr, "Contains negative cycle!\n"); continue;}
         //END EDIT
         //Searches for the cheapest way from all-to-all nodes, if new path
         // is cheaper than the previous one, its updated in matrix
         (*distanceMatrix)[from][to] = min((*distanceMatrix)[from][to],
         ((*distanceMatrix)[from][via]+(*distanceMatrix)[via][to]));
       }
 }
}
}

min は次のとおりです。

int min(int a,int b)
{return (a<b)? a:b;}

私の距離マトリックスには、コストがかからないところならどこでもINFがあります。

変更されたアルゴリズムが次のような古いトピックに出くわしました:

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

ただし、関数の代わりにこの修正を使用しても、ループが発生し、コストがさらに削減されます。この修正は正しいですか？そうでない場合、どのように書き直せばよいですか？ありがとう。

4

1 に答える 1

0

ウィキペディアより

したがって、Floyd-Warshall アルゴリズムを使用して負のサイクルを検出するには、パス マトリックスの対角線を調べることができます。負の数の存在は、グラフに少なくとも 1 つの負のサイクルが含まれていることを示します。[2] 明らかに、無向グラフでは、負のエッジは、その付随する頂点を含む負のサイクル (つまり、閉じたウォーク) を作成します。

したがって、d[k][k]これよりも小さい場合は0、終了して負のサイクルがあると言う必要があります。

于 2013-05-14T21:21:19.650 に答える