我正在寻找一种好的解决方案,以在无向且无权图中找到s-t最小割边。我想使用推送-重贴标签算法。但是我不确定如何将其实现以在无向且无权图中找到最小割。 对于每对顶点之间都有两个相反的边,并给所有边相同的权重,然后应用推送-重贴标签算法吗? 这样可以得到最小割吗?我在下面的图上尝试了它。在顶点上的a(m,n)表示e(a)=m,h(a)=n。每条边的容量都设置为1。 很明显,最小割是边缘(c,t)。但从最后一张图片中,我怎么知道(c,t)是最小割边缘?还是我计算错误了。 有人能指出我的错误吗? 欢迎提供建议,谢谢!