作者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/cn.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