作者a127a127 (TDYa127)
看板Prob_Solve
标题Re: [问题] Gabow's scaling algorithm for SSSP
时间Sun Aug 9 22:40:12 2009
1F：推 seanwu:说到SPFA，随机的情况下，复杂度应该会很低? 像qsort那样? 08/09 04:01
唔，其实一直很想问你们有没有看到相关的证明。
我看到的资料似乎都是指向大陆国家集训队2006年余远铭的《最短路算法及其应用》，
可是那篇根本没有证明，只是说一般情况下O(kE)的k是很小的常数。
接下来09年 姜碧野《SPFA算法的优化及应用》，
里面有较多的论述和数据，但仍然没有证明（还是指向06余远铭那篇）。
2F：推 DJWS:SPFA这个名词是从哪里出来的? 08/09 12:35
这也是我一直很疑惑的问题，一直没有找到外语的论文有用这个名词。
查到的全部都是大陆那边的资料，我甚至怀疑这个词只有对岸有在使用。
不过google SPFA前面几笔都是这个东西，
所以我也很乐於使用这个词，不然以前不知道怎麽讲 XD。
3F：→ DJWS:另外想问SPFA是不是CLRS习题24-1所提到的改进方式? 08/09 12:44
不是。
我所知道的SPFA，就是很简单的BFS改进。
BFS找最短路径时，走过的点如果又被更新成更小的值，
那麽：仅当此点不在Queue中，才丢进Queue里面。
4F：推 electorn:SPFA是bellman ford改进版本...个人觉得当可以用dijkstra 08/09 13:00
5F：→ electorn:的情形下，dijkstra都表现得比SPFA还要好 @@" 08/09 13:00
其实我觉得Bellman-Ford更不直觉 XD，
或是说比较像从数学的观点来看，而不是图的观点。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.70.184.165
6F：推 seanwu:嗯...那个k，一般来说真的非常小.. 甚至比dijkstra还快 08/10 03:14
7F：→ seanwu:而且很难去构造一个让SPFA跑很慢的图 08/10 03:15
8F：→ seanwu:个人经验上，很稀疏或很稠密的图，会很快 08/10 03:16
9F：→ seanwu:然後我也没有看过任何有关的证明就是了 08/10 03:18
10F：→ seanwu:要说它上不了台面也好，但总之它个非常实用的算法 08/10 03:20
11F：→ a127a127:我记得，我和tmt之前有构造过一个让k = O(V)的例子。 08/10 03:24
12F：→ a127a127:而且不怎麽复杂，不过我们没有实际用程式跑过就是了。 08/10 03:25
13F：→ a127a127:上面都是优点，我来讲些缺点好了 XD。 09年姜碧野那篇， 08/10 03:30
14F：→ a127a127:指出了：遇到网格图或阶梯图，会很慢。图的形状和值的分 08/10 03:33
15F：→ a127a127:布严重影响执行效率。 （是说跟Dijkstra比） 08/10 03:36
16F：推 LPH66:我的理解是这不过就是加了Queue可以重新relax的Dijkstra... 08/10 05:23
17F：推 LPH66:所以是不是 O(kE) 个人以为还有待讨论 08/10 05:30
18F：→ LPH66:唯一的优点就是可以处理负边而已... 08/10 05:30
19F：→ LPH66:(喔我是指和Dijkstra比起来) 08/10 05:33
20F：→ LPH66:是说如果把这个概念放回Dijstra去如何? 被relax的人如果不在 08/10 05:34
21F：→ LPH66:heap当中 (这可以设flag) 就重新enheap... 08/10 05:34
22F：→ LPH66:这样能不能把Dijkstra改成可处理负边? 08/10 05:36
24F：→ DJWS:其实就是label correcting algo.的改良版 只是没人命名吧? 08/10 13:21
26F：→ shik:朴素SPFA会爆炸的测资 08/11 02:14