Re: [問題] Gabow's scaling algorithm for SSSP
看板Prob_Solve (計算數學 Problem Solving)作者a127a127 (TDYa127)時間15年前 (2009/08/08 01:39)推噓4(4推 0噓 4→)留言8則, 4人參與討論串2/4 (看更多)
※ 引述《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
→
08/08 01:39, , 1F
08/08 01:39, 1F
推
08/08 11:19, , 2F
08/08 11:19, 2F
→
08/08 11:28, , 3F
08/08 11:28, 3F
推
08/09 04:01, , 4F
08/09 04:01, 4F
推
08/09 12:35, , 5F
08/09 12:35, 5F
→
08/09 12:44, , 6F
08/09 12:44, 6F
推
08/09 13:00, , 7F
08/09 13:00, 7F
→
08/09 13:00, , 8F
08/09 13:00, 8F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
