→ taitin:恩，我推文說錯了 02/10 10:48
※ 引述《NOtWorThy (分子小於64)》之銘言：
: 如題 中央資結95考古題 第7題
: 不知是否理解錯誤
: 或有其他想法
: 煩請高手賜教
: 謝謝!!
Floyd Algorithm計算到第k回合的時候，是判斷出頂點i~頂點j存不存在有只
使用頂點編號 < k的路徑，所以應該沒辦法拿來判斷迴圈？
所以可以用另外一種求Transitive Closure的方法，就是Adjacency Matrix相乘法。
（不是數學的乘法..）
乘一次代表頂點i到頂點j有沒有長度為2的路徑，所以乘三次之後就知道
有沒有長度為4的路徑了。時間複雜度就是跟矩陣乘法一樣，看你要用哪種演算法。
不過還有另外一種想法，如果a, b, c, d四個點形成迴圈，那麼a必定連向b, d，
且c也連向b, d，只要窮舉所有a, c對，看看他們有沒有共同相連的兩點就可以。
a, c對有O(n^2)個，而判斷共同相連的點只需要O(n)，複雜度為O(n^3)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50