如何在图中找到一条包含3条负边权的环？

Question

如何在图中找到一条包含3条负边权的环？

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:

- remo

什么语言？如果有的话，你使用哪个库？ - fge

另外，您询问是否有比O(n^3)算法更快的算法，这意味着您已经有了一个：能否提供该算法的链接？ - fge

2

@remo：如果边的数量在Ω(n²)，我认为你不能比n³更好。 - Niklas B.

1

@remo：边的数量有什么限制吗？ - Niklas B.

1

我已经阅读了聊天讨论，但仍不清楚是否实际上存在Ω(n²)条边！此外，在聊天中，OP暗示这些边是有向的，但他/她提供的代码只检查每条边的一个方向（有向三角形可以“定向”两种不同的方式）。 - j_random_hacker

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- coproc · Accepted Answer

我无法想到比O(n³)更低的复杂度算法，但实际上常数因子也很重要。以下算法允许剪枝以加快寻找负权重长度为3的循环 - 或者检查是否存在这样的循环。

按其权重对(有向)边进行排序。
选择最小权重的边作为起始边。
尝试所有连接到起始边终点的边，其权重不低于起始边(第一次剪枝)，并在关闭循环时检查权重之和。如果找到了带有负权重的长度为3的循环，则完成。
使用下一个最小权重的边作为起始边。如果它的权重为负，则转到步骤3 - 否则完成(第二次剪枝)。

思路是具有负权重和长度为3的循环中至少有一条边具有负权重。我们可以从循环中最小权重的边开始寻找循环。

如果您知道具有负权重的边数是O(n)，那么此算法的时间复杂度将为O(n² log n)，因为算法将由第1步(根据权重排序边)主导。