103高考資訊處理-資料結構第6題 - 高考

我好像摸出一點頭緒了,回來自問自答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是用在"用於檢查邊,更新最短距離",
所以執行次數為邊的總和.


--