Re: [問題] Gabow's scaling algorithm for SSSP

[a127a127 (TDYa127)]

※ 引述《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
→ a127a127:有耶～
推 DJWS:BFS應該是用在每一條邊的權重都一樣大的時候
→ a127a127:嗯，所以我有括號SPFA，被更新過的就要重來一次。
推 seanwu:說到SPFA，隨機的情況下，複雜度應該會很低? 像qsort那樣?
推 DJWS:SPFA這個名詞是從哪裡出來的?
→ DJWS:另外想問SPFA是不是CLRS習題24-1所提到的改進方式?
推 electorn:SPFA是bellman ford改進版本...個人覺得當可以用dijkstra
→ electorn:的情形下，dijkstra都表現得比SPFA還要好 @@"