Re: [問題] Gabow's scaling algorithm for SSSP
推
08/09 04:01,
08/09 04:01
唔，其實一直很想問你們有沒有看到相關的證明。
我看到的資料似乎都是指向大陸國家集訓隊2006年余遠銘的《最短路算法及其應用》，
可是那篇根本沒有證明，只是說一般情況下O(kE)的k是很小的常數。
接下來09年 姜碧野《SPFA算法的優化及應用》，
裡面有較多的論述和數據，但仍然沒有證明（還是指向06余遠銘那篇）。
推
08/09 12:35,
08/09 12:35
這也是我一直很疑惑的問題，一直沒有找到外語的論文有用這個名詞。
查到的全部都是大陸那邊的資料，我甚至懷疑這個詞只有對岸有在使用。
不過google SPFA前面幾筆都是這個東西，
所以我也很樂於使用這個詞，不然以前不知道怎麼講 XD。
→
08/09 12:44,
08/09 12:44
不是。
我所知道的SPFA，就是很簡單的BFS改進。
BFS找最短路徑時，走過的點如果又被更新成更小的值，
那麼：僅當此點不在Queue中，才丟進Queue裡面。
推
08/09 13:00,
08/09 13:00
→
08/09 13:00,
08/09 13:00
其實我覺得Bellman-Ford更不直覺 XD，
或是說比較像從數學的觀點來看，而不是圖的觀點。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.184.165
推
08/10 03:14, , 1F
08/10 03:14, 1F
→
08/10 03:15, , 2F
08/10 03:15, 2F
→
08/10 03:16, , 3F
08/10 03:16, 3F
→
08/10 03:18, , 4F
08/10 03:18, 4F
→
08/10 03:20, , 5F
08/10 03:20, 5F
→
08/10 03:24, , 6F
08/10 03:24, 6F
→
08/10 03:25, , 7F
08/10 03:25, 7F
→
08/10 03:30, , 8F
08/10 03:30, 8F
→
08/10 03:33, , 9F
08/10 03:33, 9F
→
08/10 03:36, , 10F
08/10 03:36, 10F
推
08/10 05:23, , 11F
08/10 05:23, 11F
推
08/10 05:30, , 12F
08/10 05:30, 12F
→
08/10 05:30, , 13F
08/10 05:30, 13F
→
08/10 05:33, , 14F
08/10 05:33, 14F
→
08/10 05:34, , 15F
08/10 05:34, 15F
→
08/10 05:34, , 16F
08/10 05:34, 16F
→
08/10 05:36, , 17F
08/10 05:36, 17F
推
08/10 13:18, , 18F
08/10 13:18, 18F
→
08/10 13:21, , 19F
08/10 13:21, 19F
推
08/11 02:14, , 20F
08/11 02:14, 20F
→
08/11 02:14, , 21F
08/11 02:14, 21F
→
08/11 02:17, , 22F
08/11 02:17, 22F
討論串 (同標題文章)