[問題] 演算法 Shortest Path 問題

作者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://www.ptt.cc/bbs/Programming/M.1406391891.A.AAB.html

→ suhorng:對每個點 BFS 是 O(VE)... 111.248.42.5 07/27 00:39

→ suhorng:可是 |V| < |E| < |V|^2 這條件感覺什麼也 111.248.42.5 07/27 00:39

→ suhorng:沒說呀... 111.248.42.5 07/27 00:39

→ penguin7272:右邊還可以除個二 XD... 111.252.209.63 07/27 01:01

→ scwg: math.stackexchange.com/questions/58198 128.36.232.45 07/27 02:39

→ scwg: |V| 次 BFS 是 O(|E||V|+|V|^2) 如果 |E| > 128.36.232.45 07/27 02:41

→ scwg: |V|^1.376 而且願意刻, 可以做矩陣相乘... 128.36.232.45 07/27 02:42

→ s86092x:原來如此！十分感謝 <(_ _)>140.113.216.110 07/27 07:58

推 suhorng:矩陣相乘的話實務上常數不是很大..? 111.248.42.5 07/27 10:16