[理工] floyd warshall計算！ Aa841018 PTT批踢踢實業坊

[理工] floyd warshall計算！

作者: Aa841018 (andrew) 2019-12-14 21:46:53

https://i.imgur.com/WV2F6Qb.jpg
請教一下，各位在做類似交大這種5*5、6*6的floy warshall 演算法時，都是硬幹嗎？
這題我20分鐘做不完…
這題真的太誇張，有些是5*5也是要很久，如果是求transitive closure，那只有0、1可
以快很多，那還好，像交大這題…根本不可能在30分鐘內做完吧？
有什麼方法可以加速運算時間嗎？（除了k列k行和上個矩陣相同這個以外）

作者: mi981027 (呱呱竹) 2019-12-14 22:04:00

這題因為他終點都是F 所以其實可以把所有邊reverse然後用bellman ford算F到各點的距離會快一點

作者: DLHZ ( ) 2019-12-14 22:43:00

長知識感覺很好用

作者: mistel (Mistel) 2019-12-14 22:56:00

原來有這招

繼續閱讀

[理工] 104中央數學ponwar87123 [理工] 105 成大資演 SMMHpyramidinc [理工] 中央108計算機組織與作業系統ponwar87123 [理工] OS 2題！Aa841018 [理工] 108 成大線代pyramidinc [理工] 計組 GPU 多核心mistel [理工] 資演 101交大 12題遞迴和複雜度ching4562 [理工] 資結 hashingching4562 [理工] 105 交大資演pyramidinc [理工] 108中央資演對答案ponwar87123