作者DJWS (...)
看板Prob_Solve
標題[問題] Gabow's scaling algorithm for SSSP
時間Fri Aug 7 21:37:48 2009
想請教大家的是 introduction to algorithms 的習題 24-4(a):
當以s為起點的最短路徑的距離皆小於 |E| 時,
試說明一個 O(E) 的演算法可求出此情況下的SSSP。
(我用的書是二版四刷,在616頁。)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.82.25
→ a127a127:直接從Dijkstra改就好了。 08/08 01:14
→ a127a127:找最近點時,用一個大小為E的陣列去找。(像counting sort 08/08 01:17
→ a127a127:我回文好了 順便賺個p幣 XD 08/08 01:19
→ DJWS:感謝 :D 08/08 11:21