验证四步法求解经过顶点u、v的最小权回路是否正确

该方法无法保证得到符合要求的最小权回路，存在逻辑漏洞。

我们可以构造如下无向连通图证明：

• 顶点：u、x、y、v
• 边及权值：u-x(2)、x-y(0.5)、y-v(2)、u-y(3)、x-v(3)、u-v(7)

按照你提出的步骤计算：

1. u到v的唯一最短路径为u-x-y-v，总权值为2+0.5+2=4.5，记为p1。
2. 移除p1包含的3条边u-x、x-y、y-v。
3. 剩余边中v到u的最短路径只能是直接边u-v，权值为7，记为p2。
4. 拼接得到的回路总权值为4.5+7=11.5。

但存在更优的边不重复回路：
选择两条边不相交的u-v路径u-x-v（权值2+3=5）和u-y-v（权值3+2=5），拼接后的回路总权值为5+5=10，明显小于上述方法得到的11.5。

该方法属于贪心策略，优先选择第一条最短路径，但这条路径可能占用了多条关键边，导致第二条路径的权值大幅上升，局部最优的选择最终带来全局总权值更高的结果。

如果需要得到满足要求的最小权回路，可以将问题转化为最小费用流问题：
将每条无向边拆为两条方向相反的有向边，每条边容量设为1、费用等于原边权值，求解从u到v流量为2的最小费用流，得到的总费用就是两条边不相交路径的最小总权值，对应你需要的最小权回路。

内容的提问来源于stack exchange，提问作者HervéSV