高普考題庫
103 年 103年公務人員高等考試三級考試暨普通考試・資料結構
申論 6若G=(U,E)為一權重圖(weighted graph),每條邊的權重均不為負數,則單源最短路徑問題(Single Source Shortest Path Problem)可以用著名的Dijkstra 演算法求得,回答下列問題:(每小題5 分,共15 分)說明Dijkstra 演算法的主要觀念。Dijkstra 演算法在最差情況下(Worst Case Analysis),下列三個功能Insert、Delete、Decrease_Key 各自需要執行的次數,可用Big-Oh 符號表示。若是要在O(|E|+|V|log|V|)最差情況分析下的時間內執行Dijkstra 演算法,請問該選擇使用那種資料結構,並說明其原因。