c++ - 如何在图中找到 3 条边的负加权循环？

Question

我有一个包含大约 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:

Answer 1

我想不出任何复杂度低于 O(n³) 的算法，而且常数因子在实践中也很重要。以下算法允许修剪以加快找到长度为 3 且权重和为负的循环 - 或者检查是否不存在这样的循环。

1. 根据权重对(有向)边进行排序
2. 取权重最小的边作为起始边。
3. 尝试连接到起始边的结束顶点的所有边，其权重不低于起始边(第一次修剪)，并在关闭循环时检查权重之和。如果您找到一个和为负数的循环，您就完成了。
4. 继续以权重次低的边作为起始边。如果它的权重为负转到 3 - 否则你就完成了(第二次修剪)

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

如果您知 Prop 有负权重的边的数量是 O(n) 那么这个算法将是 O(n² ld n) 因为算法将由步骤 1 支配(= 排序边缘根据它们的重量)。