看板 [ Prob_Solve ]
討論串[問題] Gabow's scaling algorithm for SSSP
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] Gabow's scaling algorithm for SSSP
推噓0(0推 0噓 4→)留言4則，0人參與, 最新作者DJWS (...)時間15年前 (2009/08/07 21:37), 編輯資訊
1
0
0
內容預覽:
想請教大家的是 introduction to algorithms 的習題 24-4(a):. 當以s為起點的最短路徑的距離皆小於 |E| 時，. 試說明一個 O(E) 的演算法可求出此情況下的SSSP。. (我用的書是二版四刷，在616頁。). --. ※ 發信站: 批踢踢實業坊(ptt.cc)
#2
Re: [問題] Gabow's scaling algorithm for SSSP
推噓4(4推 0噓 4→)留言8則，0人參與, 最新作者a127a127 (TDYa127)時間15年前 (2009/08/08 01:39), 編輯資訊
1
0
0
內容預覽:
一開始. dis. ┌──┐. │ 0 │ --> s. ├──┤. │ 1 │ --> NULL. ├──┤. │ . │. │ . │. │ . │. ├──┤. │ E-2│ --> NULL. ├──┤. │ E-1│ --> NULL. └──┘. 找最近的點的時候，從0開始跑到E-1。.
(還有78個字)
#3
Re: [問題] Gabow's scaling algorithm for SSSP
推噓5(5推 0噓 17→)留言22則，0人參與, 最新作者a127a127 (TDYa127)時間15年前 (2009/08/09 22:40), 編輯資訊
1
0
0
內容預覽:
唔，其實一直很想問你們有沒有看到相關的證明。. 我看到的資料似乎都是指向大陸國家集訓隊2006年余遠銘的《最短路算法及其應用》，. 可是那篇根本沒有證明，只是說一般情況下O(kE)的k是很小的常數。. 接下來09年 姜碧野《SPFA算法的優化及應用》，. 裡面有較多的論述和數據，但仍然沒有證明（還是
(還有170個字)
#4
Re: [問題] Gabow's scaling algorithm for SSSP
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者DJWS (...)時間15年前 (2009/08/10 13:54), 編輯資訊
0
0
0
內容預覽:
當然可以囉，經過修正之後，. 這整件事就變成了SPFA，只是容器從queue變成了heap而已。. 更進一步來說，這個修正，其實是把整個演算法. 由label setting改成label correcting，並沒有什麼特別的。. 有負邊的情況下，label setting的演算法本來就會失效，.
首頁
上一頁
1
下一頁
尾頁