資料集：City of Oldenburg (OL) Road Network
9組查詢均為相距較遠的結點
最近一直在圍繞雙向迪傑斯特拉轉，對其中重要的優先隊列資料結構，嘗試了用無索引的二叉堆實作、有索引的二叉堆實作以及無索引的斐波那契實作三種方式。其中無索引的優先隊列允許出現相同的節點，而有索引的優先隊列中不允許。不同實作方式運作時間如表2-1所示，其中每個查詢都運作了10000次，機關ms。
表2-1 雙向迪傑斯特拉不同優先隊列實作方式運作結果
查詢
雙向迪傑斯特拉
二叉堆無索引t1
二叉堆有索引t2
t2/t1
斐波那契堆無索引
1
873
1716
1.96
1982
2
4103
8065
11466
3
6615
10842
1.63
17207
4
2106
3448
5460
5
5444
8674
1.59
14804
6
3666
6052
1.65
10046
7
655
1092
1.66
1264
8
4212
6662
1.58
11840
9
6272
9578
1.52
16365
問題1： 無索引的二叉堆比有索引實作優先隊列最短路徑求解快了平均1.7倍。其中對于索引部分嘗試了兩種方式：數組索引與哈希（cmap）索引，兩種方式效果相似。
分析： 建立、調整索引的時間與存儲結點的時間是一樣的，是以加入索引必然增加優先隊列的時間消耗。
另外，對于無索引的優先隊列，相同的結點會同時出現在隊列中。對于相同的節點，先出來的肯定是最小的，當其它結點出來時到該節點的最短路徑已經求出，隻需一次判斷即可。而實際中隻有小于20%的出隊列操作是無效的。
無索引的二叉堆雙向迪傑斯特拉主要函數運作時間分析如圖2-1所示。函數調用關系如圖2-2所示。
圖2-1 各主要函數運作時間
圖2-2 重要路徑
對于迪傑斯特拉來說，使用優先隊列比普通方法快近60倍。是以對比中直接忽略該種方式實作的迪傑斯特拉。表3-1列出了查詢時間，其中每組查詢都運作了10000次，其中優先隊列的實作方式為無索引的二叉堆。
表3-1 無索引的雙向迪傑斯特拉與迪傑斯特拉時間對比
迪傑斯特拉
2262
6911
7425
7207
1872
1154
7051
7489
問題2：對于查詢4與查詢7雙向迪傑斯特拉比迪傑斯特拉慢。
分析： 雙向迪傑斯特拉相比于迪傑斯特拉減少了一些結點的最短路徑計算，即減少了處理結點。但是，前者需要多次的加法操作，也消耗了大量的時間。
問題3： 當求解所有點對的最短路徑時，floyd比迪傑斯特拉與雙向迪傑斯特拉都快。
分析： floyd求解的時候不存在重複計算問題；而多次運作單源點最短路徑問題求解所有對的最短路徑時，存在很多重複的計算。是以，求解所有對或者多對最短路徑時floyd算法優于迪傑斯特拉和雙向迪傑斯特拉。