最小环

引入

问题

给出一个图，问其中的由 $n$ 个节点构成的边权和最小的环 $(n\ge 3)$ 是多大。

图的最小环也称围长。

过程

暴力解法

设 $u$ 和 $v$ 之间有一条边长为 $w$ 的边，$dis(u,v)$ 表示删除 $u$ 和 $v$ 之间的连边之后，$u$ 和 $v$ 之间的最短路。

那么无向图中的最小环是 $dis(u,v)+w$。

注意若是在有向图中求最小环，相对应的公式要修改，最小环是 $dis(v,u)+w$。

总时间复杂度 $O(n^{2}m)$。

Dijkstra

相关链接：最短路/Dijkstra

过程

枚举所有边，每一次求删除一条边之后对这条边的起点跑一次 Dijkstra，道理同上。

性质

时间复杂度 $O(m(n+m)\log n)$。

Floyd

相关链接：最短路/Floyd

过程

记原图中 $u,v$ 之间边的边权为 $val(u,v)$。

我们注意到 Floyd 算法有一个性质：在最外层循环到点 $k$ 时（尚未开始第 $k$ 次循环），最短路数组 $dis$ 中，$di{s}_{u,v}$ 表示的是从 $u$ 到 $v$ 且仅经过编号在 $[1,k)$ 区间中的点的最短路。

由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 $w$，环上与 $w$ 相邻两侧的两个点为 $u,v$，则在最外层循环枚举到 $k=w$ 时，该环的长度即为 $di{s}_{u,v}+val(v,w)+val(w,u)$。

故在循环时对于每个 $k$ 枚举满足 $i

---

本页面最近更新：2025/7/30 21:25:22，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Tiphereth-A, ywwywwyww, Enter-tainer, greyqz, iamtwz, ksyx, cesonic, Doubeecat, Early0v0, GoodCoder666, Marcythm, Menci, PeterlitsZo, shawlleyw, sshwy, sun2snow, u5n, Xeonacid, ZnPdCo
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用