作者s86092x (Dust)
看板Programming
標題[問題] 演算法 Shortest Path 問題
時間Sun Jul 27 00:24:49 2014
各位大大您好：
小弟最近寫程式遇到演算法 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，所以我有這個疑問，
如果有什麼條件忘了附帶麻煩告知，
十分感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.216.110
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Programming/M.1406391891.A.AAB.html
1F：→ suhorng:對每個點 BFS 是 O(VE)... 111.248.42.5 07/27 00:39
2F：→ suhorng:可是 |V| < |E| < |V|^2 這條件感覺什麼也 111.248.42.5 07/27 00:39
3F：→ suhorng:沒說呀... 111.248.42.5 07/27 00:39
4F：→ penguin7272:右邊還可以除個二 XD... 111.252.209.63 07/27 01:01
5F：→ scwg: math.stackexchange.com/questions/58198 128.36.232.45 07/27 02:39
6F：→ scwg: |V| 次 BFS 是 O(|E||V|+|V|^2) 如果 |E| > 128.36.232.45 07/27 02:41
7F：→ scwg: |V|^1.376 而且願意刻, 可以做矩陣相乘... 128.36.232.45 07/27 02:42
8F：→ s86092x:原來如此！ 十分感謝 <(_ _)>140.113.216.110 07/27 07:58
9F：推 suhorng:矩陣相乘的話實務上常數不是很大..? 111.248.42.5 07/27 10:16