4

約 10,000 ノードの有向グラフがあります。すべてのエッジが重み付けされます。3 つのエッジのみを含む負のサイクルを見つけたいです。O(n^3) より速いアルゴリズムはありますか?

サンプルコード: (g は私のグラフ)

if (DETAILS) std::printf  ("Calculating cycle of length 3.\n");
for (int i=0;i<NObjects;i++)
{
    for (int j=i+1;j<NObjects;j++)
    {
        for (int k=j+1;k<NObjects;k++)
        {
            if ((d= g[i][j]+g[j][k]+g[k][i])<0)
            {
                results[count][0] = i;
                results[count][1] = j;
                results[count][2] = k;
                results[count][3] = d;
                count++;
                if (count>=MAX_OUTPUT_SIZE3)
                    goto finish3;
            }

            if ((d= g[i][k]+g[k][j]+g[j][i])<0)
            {
                results[count][0] = j;
                results[count][1] = i;
                results[count][2] = k;
                results[count][3] = d;
                count++;
                if (count>=MAX_OUTPUT_SIZE3)
                    goto finish3;
            }
        }

    }
}
finish3:
4

1 に答える 1

4

O(n 3 )よりも明確な複雑さを持つアルゴリズムは考えられませんが、定数係数も実際には重要です。次のアルゴリズムを使用すると、重みの合計が負である長さ 3 のサイクルを見つけたり、そのようなサイクルがないことを確認したりして、枝刈りを高速化できます。

  1. 重みに従って (有向) エッジを並べ替える
  2. 重みが最小のエッジを開始エッジとして使用します。
  3. 開始エッジよりも低くない重みで開始エッジの終了頂点に接続されているすべてのエッジを試し (1 回目の枝刈り)、サイクルを閉じるときに重みの合計を確認します。合計が負のサイクルが見つかった場合は完了です。
  4. 次に重みが小さいエッジを開始エッジとして続行します。その重みが負の場合は goto 3 - そうでない場合は完了です (2 回目の刈り込み)

この考え方は、合計が負の円環のエッジの少なくとも 1 つが負の重みを持つ必要があるというものです。そして、サイクル内で最小の重みでエッジからサイクルを開始できること。

負の重みを持つエッジの数が O(n) であることがわかっている場合、このアルゴリズムは O(n 2 ld n) になります。これは、アルゴリズムがステップ 1 (= 重みに従ってエッジを並べ替える) によって支配されるためです。

于 2012-12-29T16:55:09.247 に答える