作者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
1F：→ a127a127:直接从Dijkstra改就好了。 08/08 01:14
2F：→ a127a127:找最近点时，用一个大小为E的阵列去找。(像counting sort 08/08 01:17
3F：→ a127a127:我回文好了 顺便赚个p币 XD 08/08 01:19
4F：→ DJWS:感谢 :D 08/08 11:21