Dijkstra算法中第（2）、（3）步的計算和比較結果沒有保存下來，並且每次隻選取d中最小的一個，所有沒有選中的未標記的節點在下一次要重新計算dj並查找出一個d中最小的一個。如果把dj保存在每個節點中，並且把待比較的節點按序放到一個有序鏈表中，則插入/比較的時間將大大縮短。
根據圖中頂點和邊的個數可以求出頂點的平均出度e=m/n（m為邊數，n為頂點數），這個數值代表了圖的連通程度，一般在GIS網絡圖中，e∈[2，5]，這樣如果當前永久標記的節點的出度為t，那麼，下一步需掃描的點的個數就約為0～t個，時間複雜度降為O（1）。
1.3 本文提出的最短路徑快速算法
1.3.1 算法描述
所有的節點分為三種狀態，即未標記（US）、即將標記（TS）和已標記（AS）三種狀態。每個節點都有一對標號（dj，pj），其中dj是從源點s到點j的最短路徑的長度（不包括頂點到其本身）；pj則是從s到j的最短路徑中j點的前一點。
（1）初始化。①創建TS隊列並清空②標記起源點s為AS狀態③標記起源點s的所有出邊點j的狀態Sj為TS，入TS隊列，其中dj= lsj，TS隊列按照dj的值從小到大有序排列 ④其他所有點設為US狀態。
（2）取TS隊列的第一個節點i（當前最小值），標記i為AS狀態，並把i從TS隊列中刪除，若i為終點，轉到（5）。
（3）判斷i的所有出邊點j的狀態：若Sj =US，則dj=di+lij，pj=i，節點j按dj的大小入TS隊列；否則若Sj=TS，並且dj>；di+lij，則dj=di+lij，修改pj=i，節點j按dj的大小重新排序。
（4）若TS隊列為空，轉向（5），否則轉到（2）繼續。
（5）算法結束。若i為終點，找到最短路徑；否則若TS隊列為空，起點和終點不連通。
1.3.2 時間複雜度分析
由於兩點之間最短路徑的計算次數隨兩點之間經過的節點數不同而不同，使得各種輸入集出現的概率難以確定，在這裏我們討論算法在最壞情況下的時間複雜度。整個算法為一重循環，循環次數為n （m最大為n）。算法的循環體部分是從第（2）到第（4）步，其中第2和4步的時間複雜度顯然為O（1），關鍵是分析第（3）步。第（3）步中把i的的所有出邊點依次有序插入TS隊列，其時間複雜度取決於TS隊列的規模，設TS隊列的平均大小為，由以上1.2節分析可知遠小於，在最壞情況下，的值大約為115，還是非常小的，因此第（3）步的時間複雜度為O（）。所以總的時間複雜度為O（（1+ +1）*n）=O（n），因此本文提出的算法的時間複雜度僅與節點數n成線性關係，與Dijkstra的時間複雜度O（n2）相比，效率提高很多。
2 改進的最短路徑算法的具體實現
按照以上思路，筆者用Visual C++實現了上海黃頁最短路徑模塊中最短路徑算法。以上海市區道路為數據（共7 038個節點，9 365條弧段），計算一條貫穿全城的線路，在普通微機上約需0.1 s。
2.1 數據結構的設計
矢量地圖存儲的方法很多，如鄰接矩陣、鄰接表等。用這些常用的方法存儲交通網絡，存儲量龐大，而且不利於網絡操作。文獻[6]提出的以交通節點為基礎的數據結構，雖然克服了上述缺點，但是文獻[6]隻考慮節點以及節點之間的關係，對於弧段之間的關係沒有考慮。而在實際應用中，大多數GIS網絡都是有向帶權圖，如道路有單雙向問題，從一個弧段到其相鄰弧段常有轉向限製等。如果我們采用轉向表來表示弧段之間的轉向關係，勢必會造成存儲容量激增，並且在計算最短路徑時每一步都要查找轉向表，以確定哪個弧段可以轉向，造成算法很多不必要的時間開銷。
為了能夠清晰簡單的表示弧段之間的轉向關係，在節約存儲空間的前提下，本文不采用轉向表。在實現本文提出的算法時，我們把節點和節點之間的關係改成弧段和弧段之間的關係，使道路之間的聯係更加清晰直接，從而方便計算最短路徑。
我們設計了兩個類來表示弧段以及弧段之間的聯係，分別是類CArc和類CArcLink。類CArc包括弧段的狀態sj，從起源弧段s到弧段j的最短路徑長度dj （包括s和j的長度），起源弧段s到弧段j的最短路徑中j的前一弧段pj，該弧段的權值（該弧段的長度或耗費的時間）；類CArcLink包括弧段之間的轉向阻抗，從A弧段能否轉向至B弧段的標誌位（開關屬性）等。