大家好，最近在学Maximum Flow时学到这个算法，
这个算法说到，在每次更新路径(流量)的时候，
要选择最最小的那一条，我看了手边的范例，
无法理解他所说的最小的那一条是怎么算出来的，
http://tinyurl.com/azefzfp
这个是我在网络上找到的一个范例投影片，
第五页的部分，他的选择是 s -> 3 -> 5 -> 4 -> t 流量是6
为什么不选择 s -> 3 -> 2 -> 4 -> t 流量是2呢?
谢谢

s -> 3 -> 5 -> 4 -> t 中经过的残余容量是10 7 6 10里面最小的是 5 -> 4 的 6. 他说的最小是这个你看 5->4 那一条的箭头特别粗

你记错前提了，Ford-Fulkerson 没有要求要最小的那条看了楼上才知道原来误会是在那里 :p

那请问可以走我说的那一条吗?经过1F的说明，我现在的认知是，只要任选一条走S到T那一条路径的流量是当中最小的就可以了?那另外请问，这个例子当中的，min cut是否是指

可以，但你上面这句应该是错的。

找出max flow之后，s点还可以走到3，而s和3连接到其他的点所构成的边就是min cut

最小是指,path可增加的流量,是所有经过edge中剩余流量最小的

也就是S到2和3到5 这两条?t大我解你所说的，我上面用字不精确造成误会

正确

相当感谢