作者booowei1203 (wei)
看板Grad-ProbAsk
標題[理工] 100 交大 Floyd-Warshall 負weight cycle
時間Thu Dec 10 15:58:02 2020
https://imgur.com/FalqPUB
106師大資工 這題的C小題，
如果 floyd warshall 的最後一個矩陣的對角線元素有負值的話，
代表該圖有negative weight cycle
https://imgur.com/wJ4pD5H
但是交大100 這題的第2小題的d選項說
「floyd warshall 不能偵測 negative weight cycle」，卻沒有被選為錯的。
是不是答案有問題呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.112.71 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607587084.A.0A0.html
→ sososlee: 交大那題選項說他是錯的，所以可以偵測負環 12/10 18:31
推 sososlee: 看錯，我也覺得d可以選 12/10 18:38
推 mathtsai: 上網查了 對角線有負值代表有負環 12/10 21:28
→ yuai9111: 我是這樣想 師大題目:用floyd的"output"去detect有無負 12/11 00:12
→ yuai9111: 環 交大那題是floyd的"algo"能否判斷負環 所以d沒選 12/11 00:13
→ yuai9111: 有錯請糾正 12/11 00:14
根據答案也只能這樣解釋了，但如果出題教授真的是想表達這種觀念的話，我會暈倒XD
※ 編輯: booowei1203 (114.136.240.33 臺灣), 12/11/2020 11:14:13