h*********n
发帖数: 915 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: heavyburden (nothing), 信区: JobHunting
标 题: Dijkstra SSSP@CLR的疑问
发信站: BBS 未名空间站 (Fri Dec 14 12:07:54 2007)
这个算法基本想法是用一个优先队列，每次取最小的节点，然后修改相邻节点的key。
直到队列为空。
我的疑问是，在修改了相邻节点之后，优先队列的性质已经无法保持了。比如如果是用
堆实现的优先队列，那么修改过key之后需要重新建堆才行。
但是这一步在哪里完成呢？算法里没有，在extractMin里？但这本书上关于堆的
extractMin是先取最小值，再重建堆。当然，可以额外加一步，在取最小值之前多建一
次堆也不影响复杂度。但是这样对通用的堆操作来说效率不高。
有哪位牛牛能解释解释？ |
z*l
发帖数: 30 | 2 did you read thru the section? It mentioned that use DecreaseKey operation
to
update the key values. Each edge may incur one DecreaseKey with time
complexity of O(lgV). Each vertex will incur one ExtractMin with time
complexity of O(lgV).
The total is O(ElgV + VlgV). To improve this bound, they further introduce
Fib Heap to make the total complexity O(E + VlgV).
【在 h*********n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: heavyburden (nothing), 信区: JobHunting
: 标 题: Dijkstra SSSP@CLR的疑问
: 发信站: BBS 未名空间站 (Fri Dec 14 12:07:54 2007)
: 这个算法基本想法是用一个优先队列，每次取最小的节点，然后修改相邻节点的key。
: 直到队列为空。
: 我的疑问是，在修改了相邻节点之后，优先队列的性质已经无法保持了。比如如果是用
: 堆实现的优先队列，那么修改过key之后需要重新建堆才行。
: 但是这一步在哪里完成呢？算法里没有，在extractMin里？但这本书上关于堆的
: extractMin是先取最小值，再重建堆。当然，可以额外加一步，在取最小值之前多建一
|
j***n
发帖数: 301 | 3 z@n~
【在 z*l 的大作中提到】
: did you read thru the section? It mentioned that use DecreaseKey operation
: to
: update the key values. Each edge may incur one DecreaseKey with time
: complexity of O(lgV). Each vertex will incur one ExtractMin with time
: complexity of O(lgV).
: The total is O(ElgV + VlgV). To improve this bound, they further introduce
: Fib Heap to make the total complexity O(E + VlgV).
|
h*********n
发帖数: 915 | 4 呵呵，谢谢了。我在复习，所以只是大致抓算法看了看，然后写点算法。确实没仔细读
文字。
【在 z*l 的大作中提到】
: did you read thru the section? It mentioned that use DecreaseKey operation
: to
: update the key values. Each edge may incur one DecreaseKey with time
: complexity of O(lgV). Each vertex will incur one ExtractMin with time
: complexity of O(lgV).
: The total is O(ElgV + VlgV). To improve this bound, they further introduce
: Fib Heap to make the total complexity O(E + VlgV).
|
