推 chiuchang: 是不是做Floyd-Worshall O(n^3) 02/14 23:30
推 chiuchang: 喔不對 是不是對每個點都做一次dijkstra 每一次的dijks 02/14 23:33
→ chiuchang: tra都紀錄最長距離 所以複雜度才是O(n^3) 02/14 23:33
推 alan23273850: 難保沒有比 n^2 更快的演算法？ 02/15 09:57
→ starQJ: 所以說是因為花費的時間比較長所以選擇最高時間複雜度？ 02/15 14:31
推 chiuchang: 這題是因為題目已經說資料結構是使用array來maintain 02/15 14:42
→ chiuchang: 所以時間複雜度才是O(n^3) 02/15 14:42
→ starQJ: 為什麼是陣列就是O(n^3)？ 02/15 16:45
推 chiuchang: 因為用陣列來作為資料結構會使得dijkstra執行的時間為O 02/16 10:22
→ chiuchang: (n^2) 又執行dijkstran次所以為n*O(n^2) = O(n^3) 02/16 10:22
→ starQJ: 了解了！謝謝 02/16 11:22