algorithm - 在图中寻找最短的 4 边循环

Question

我想在加权有向图中找到恰好由 4 条边组成的最短循环(最短 = 边的权重的最小总和)。

我知道我可以使用 Floyd–Warshall 算法在图中找到最短循环，如所述 here .但是我不知道如何找到正好由四个边组成的最短循环。

Answer 1

既然你提到了 Floyd-Warshall，我认为拥有邻接矩阵不是问题。

让我们这样看:长度为 4 的循环具有 a->b->c->d->a 的形式。将其分成两对两条边:a->b->c 和 c->d->a。

给定邻接矩阵，我们可以很容易地使用恰好两条边计算最短路径矩阵:从 x 到 z 的最短路径是 的最小值x->y->z 用于每个顶点 y。如果我们需要呈现循环，而不仅仅是它的长度，那么给出最小值的顶点 y 也可以被存储。

现在，要找到长度为 4 的最短循环，只需遍历所有可能的对 (a, c)。对于每个这样的对，我们有从 a 到 c 恰好两条边的最小成本和从 c 到 c 的最小成本a 恰好有两条边。这两个成本之和最小的一对给了我们想要的周期。

解决方案的运行时间为 O(n^3)，额外内存为 O(n^2)。