我好像摸出一点头绪了,回来自问自答XD
若 G=(U,E)为一权重图（weighted graph），每条边的权重均不为负数，则单源最短路径
问题（Single Source Shortest Path Problem）可以用著名的 Dijkstra 算法求得，
回答下列问题：
(一)说明 Dijkstra 算法的主要观念。
(二)Dijkstra 算法在最差情况下（Worst Case Analysis），下列三个功能 Insert、
Delete、Decrease_Key 各自需要执行的次数，可用 Big-Oh 符号表示。
(三)若是要在O(|E|+|V|log|V|)最差情况分析下的时间内执行 Dijkstra 算法，请问该
选择使用那种资料结构，并说明其原因。
第(二)小题>>
Insert Delete Decrease_Key
高点答案 O(|V|) O(|V|) O(|E|)
公职王答案 O(1) O(VlogV) O(1)
问题1:想请问哪个答案才是正确的?
以下我原来的想法(深蓝色的部分)是错的!
我自己是偏向高点的答案,
因为题目有说是在最差情况下的执行次数,
而 Dijkstra 算法的资料结构如为一般heap,
insert/delete/decrease_key,所需花费的时间都是O(log n),
如使用F-heap,除了delete依旧需要O(log n),
其余的所需花的时间都是O(1),
所以依题意我比较可以理解高点的答案.
后来再我多翻了几次参考书,还是一样偏向高点的答案,
但原因跟上面不一样.
我新的想法是:
1.Dijkstra算法可分为
Insert 用于加入新选择的点
Delete 用于选出离出发点边最小的点
Decrease_key 用于检查边,更新最短距离
2.Dijkstra算法如果使用资料结构:邻接串行 + Fibonacci heaps(F-heaps)
每次执行时间和执行次数为
每次执行时间 执行次数
Insert O(log|V|) O(|V|)
Delete O(1) O(|V|)
Decrease_key O(1) O(|E|)
3.总时间 = 每次执行时间*执行次数
= O(log|V|)*O(|V|) + O(1)*O(|V|) + O(1)*O(|E|)
= O(|V|log|V|+|V|+|E|) |V|太小可省略
= O(|E|+|V|log|V|)
从上面三点可以发现,
高点的答案是执行次数,
公职王的答案则是每次执行时间,
所以我觉得高点的答案比较切合题意!
而其中第三点可以回答第(三)小题,
如果所花总时间为O(|E|+|V|log|V|),
资料结构应为邻接串行 + Fibonacci heaps
问题2:另外想请问为什么Decrease_Key的时间复杂度是O(|E|)?
应该说Decrease_Key的执行次数是O(|E|),
因为Decrease_Key是用在"用于检查边,更新最短距离",
所以执行次数为边的总和.