[理工] 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