[問題] 演算法 Shortest Path 問題

作者: s86092x (Dust)   2014-07-27 00:24:49
各位大大您好:
小弟最近寫程式遇到演算法 Shortest Path 的問題,
我會用到的 Graph V 和 E 的關係是 |V| < |E| < |V平方|
然後每條 E 的 Cost 都是 1,
目的是 All Pairs Shortest Paths
希望時間複雜度越低越好
有找到兩個最出名的演算法 Floyd-Warshall Algorithm 和 Johnson's Algorithm
Johnson's Algorithm 對我的 Case 感覺比較好,因為我的 E 較少
我想請問還有沒有更好的演算法,或是基礎的演算法可以讓時間複雜度更低
因為我的每條 E 的 Cost 都是 1,所以我有這個疑問,
如果有什麼條件忘了附帶麻煩告知,
十分感謝!

Links booklink

Contact Us: admin [ a t ] ucptt.com