[理工] 演算法ford-Fulkerson 觀念

[qazwsxedc597 (Deus)]

https://i.imgur.com/tY5SzNU.jpg

我想問書中說的這種情況如果都是用DFS去找path

最差的情況為什麼會第一次走suvt,第二次卻走svut而不會走sut,我知道他要表達的
意思,但是他給的例子我不是很理解,dfs第一次先選u第二次會換成先選v?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.175.99.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607635756.A.F01.html
→ aa871220: 從residual network看 一開始選svut就會只剩一條suvt能
→ aa871220: 選然後一直循環下去
推 alex391a: 樓上 沒有吧 suvt 過後下一輪還是有sut 可以選
→ alex391a: 題目沒有說用什麼方式取 只是想表達最壞情況而已 沒什麼
→ aa871220: Sor腦袋混沌== 反正他就表達隨機選augmenting path是很
→ aa871220: 爛的方法
※ 編輯: qazwsxedc597 (223.138.119.2 臺灣), 12/11/2020 11:41:21
→ mathtsai: 他想表達的就是如果p選得很爛 你的程式可能會炸掉