作者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