作者a127a127 (TDYa127)
看板Prob_Solve
标题Re: [问题] Gabow's scaling algorithm for SSSP
时间Sat Aug 8 01:39:26 2009
※ 引述《DJWS (...)》之铭言：
: 想请教大家的是 introduction to algorithms 的习题 24-4(a):
: 当以s为起点的最短路径的距离皆小於 |E| 时，
: 试说明一个 O(E) 的演算法可求出此情况下的SSSP。
: (我用的书是二版四刷，在616页。)
一开始
dis
┌──┐
│ 0 │ --> s
├──┤
│ 1 │ --> NULL
├──┤
│ . │
│ . │
│ . │
├──┤
│ E-2│ --> NULL
├──┤
│ E-1│ --> NULL
└──┘
找最近的点的时候，从0开始跑到E-1。
看那格有没有指到东西。
有的话，那个点就是最近点，
没有的话，dis的index就加1，继续找。
（整个演算法只跑一次）
每次被更新距离以後，就把这个点移到所属的dis串列中。
（就是距离k就放进dis[k]）
其实我觉得应该有更简单的方法@.@a？
或许单纯的BFS，实际分析起来就只需要O(E)？（SPFA）
--
有没有100p？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.70.184.165
1F：→ a127a127:有耶～ 08/08 01:39
2F：推 DJWS:BFS应该是用在每一条边的权重都一样大的时候 08/08 11:19
3F：→ a127a127:嗯，所以我有括号SPFA，被更新过的就要重来一次。 08/08 11:28
4F：推 seanwu:说到SPFA，随机的情况下，复杂度应该会很低? 像qsort那样? 08/09 04:01
5F：推 DJWS:SPFA这个名词是从哪里出来的? 08/09 12:35
6F：→ DJWS:另外想问SPFA是不是CLRS习题24-1所提到的改进方式? 08/09 12:44
7F：推 electorn:SPFA是bellman ford改进版本...个人觉得当可以用dijkstra 08/09 13:00
8F：→ electorn:的情形下，dijkstra都表现得比SPFA还要好 @@" 08/09 13:00