最小环问题

本文主要是介绍最小环问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题定义

从一个点出发,经过一条简单路径回到起点成为环.图的最小环就是所有环中长度最小的

解决思路

在所有环中取最小值，按照集合的思路，首先对环进行分类-按照环上点的最大编号来对整个集合进行划分
Floyd算法的最外层循环恰好对更新一条线路的节点编号做出了限制，假设此时外层循环k=c(此时指刚刚结束k为c-1时的更新操作，还未进行k为c的操作)，对于一对和点(i, j)(这里我们只考虑小于c的i和j)，它们路径中间的点的编号最大可能值为c-1，一定小于c(这就是所谓的Floyd的限制)。此时最少有i和j两点，如果想得到环上最大编号为c的环，只需要让c加入。这样就构造出环上点的最大编号为c的一种情况，枚举完所有合法的i和j，就能得到环上点的最大编号为c的所有情况(即集合的一部分划分)。枚举完k的所有值，就得到了整个集合中的所有情况。期间维护一个环路径长度的最小值即为答案。细化描述见下。

Floyd算法保证了最外层循环到 \(k\) 时所有顶点间已求得以 \(0...k-1\) 为中间点的最短路径。一个环至少有 3 个顶点,设某环编号最大的顶点为 \(L\) ,在环中直接与之相连的两个顶点编号分别为 \(M\) 和 \(N\) \((M,N < L)\),则最大编号为 \(L\) 的最小环长度即为 \(Graph(M,L) + Graph(N,L) +Dist(M,N)\) ,其中 \(Dist(M,N)\) 表示以 \(0...L-1\) 号顶点为中间点时的最短路径,刚好符合 Floyd算法最外层循> 环到 \(k=L\) 时的情况,则此时对 \(M\) 和 \(N\) 循环所有编号小于 \(L\) 的顶点组合即可找到最大编号为 \(L\) 的最小环。再经过最外层 \(k\) 的循环,即可找到整个图的最小环。

这里有一个不容易理解点是\(Graph(M,L) + Graph(N,L) + Dist(M,N)\)，为什么会分为\(Graph\)和\(Dist\)，两者的区别在哪里。
想要理解这个，必须明确(M, N)和L的位置关系，上述中提到M和N与L是直接相邻的。所谓直接相邻就是M和N到L的路径上没有其它点了，所以不能使用更新后的距离，因为更新后路径上可能包含其它点。
可以容易想到更新后的路径可以使得环的长度变小，假设我们选择了更新后的路径，且设为\(M->p_1->L\)和\(N->p_2->L\)，此时和L直接相邻的点为\(p_1\)和\(p_2\)。但是和L直接相邻的点为\(p_1\)和\(p_2\)我们是可以枚举到的。
所以说我们指定M和N与L直接相邻，虽然可能获得的不是最短距离，但是我们这样做是为了枚举到所有情况的，不需要担心最优解的问题。

代码实现

这篇关于最小环问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！