[理工] 100 交大 Floyd-Warshall 負weight cycle booowei1203 PTT批踢踢實業坊

[理工] 100 交大 Floyd-Warshall 負weight cycle

作者: booowei1203 (wei) 2020-12-10 15:58:02

https://imgur.com/FalqPUB
106師大資工這題的C小題，
如果 floyd warshall 的最後一個矩陣的對角線元素有負值的話，
代表該圖有negative weight cycle
https://imgur.com/wJ4pD5H
但是交大100 這題的第2小題的d選項說
「floyd warshall 不能偵測 negative weight cycle」，卻沒有被選為錯的。
是不是答案有問題呢？

作者: sososlee (堯) 2020-12-10 18:31:00

交大那題選項說他是錯的，所以可以偵測負環看錯，我也覺得d可以選

作者: mathtsai (mathtsai) 2020-12-10 21:28:00

上網查了對角線有負值代表有負環

作者: yuai9111 (PlayBoyYuAi) 2020-12-11 00:12:00

我是這樣想師大題目:用floyd的"output"去detect有無負環交大那題是floyd的"algo"能否判斷負環所以d沒選有錯請糾正

繼續閱讀

[理工] 線代函數唯一性aa871220 [理工] 107台大電機離散（6）（11）jimmylin1024 [理工] 計組（下）p.175sososlee [理工] 108 台大電機丙複選題joywilliamjo [理工] 線代 rank相關 109清大數學ff00662299 [理工] 考古題作業系統Race condition LaLaplace [理工] 106 台大電機丙資結joywilliamjo [理工] 離散成大108數學try66889 [理工] 108 交大資演 reductionaa871220 [理工] 104 台大電機丙 DS 資結 11題joywilliamjo