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. 尝试连接到起始边的结束顶点的所有边，其权重不低于起始边（第一次修剪），并在关闭循环时检查权重总和。如果你找到一个负和的循环，你就完成了。
  4. 继续以具有下一个最低权重的边缘作为起始边缘。如果它的权重为负 goto 3 - 否则你就完成了（第二次修剪）

这个想法是，具有负和的循环的至少一个边缘必须具有负权重。我们可以在循环中权重最低的边缘开始一个循环。

如果您知道具有负权重的边数为 O(n)，那么该算法将为 O(n 2 ld n)，因为该算法将由步骤 1 主导（= 根据其权重对边进行排序）。

于 2012-12-29T16:55:09.247 回答