矢量地圖中一種求最短路徑的快速算法
學術研究
作者：殷雯 馬佩勳
摘 要：在分析總結了經典Dijkstra算法的基礎上，提出了求最短路徑的一種快速實現算法，根據算法的複雜度與網絡節點數n成線性關係即O（n）的特點，給出了該算法的具體實現結構。
關鍵詞：最短路徑算法；城市道路網絡；地理信息係統；經典Dijkstra算法
中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2015）09-00-03
0 引 言
最短路徑問題（SP）是最基本的網絡優化問題之一，在交通網絡分析係統中占有重要地位，是其它網絡優化算法的基礎。最短路徑問題在實際中常用於汽車導航係統以及各種應急係統，這些係統一般要求到目的地的最佳路線所用時間盡可能短，並且要求根據交通狀況進行實時計算。經典的最短路徑算法——Dijkstra算法是目前多數係統解決最短路徑問題采用的理論基礎，不同係統對Dijkstra算法采用了不同的實現方法。本文以經典Dijkstra算法為理論基礎，在對矢量地圖進行大量分析、實驗的基礎上，提出最短路徑的一種快速實現算法，算法的複雜度與網絡節點數n成線性關係，即O（n），與經典Dijkstra算法的O（n2）相比，提高了算法的實用性。
1 最短路徑快速實現算法
1.1 經典Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假設每個點都有一對標號（dj ， pj），其中dj是從源點s到點j的最短路徑的長度（不包括頂點到其本身）；pj則是從s到j的最短路徑中j點的前一點，k為已標記節點的集合。求解從源點s到點j的最短路徑算法的基本過程如下：
（1）初始化。源點設置為：ds=0，ps為空；所有其它點：di=∞，pi=？；標記源點s，記k ={s}，其他所有點設為未標記。
（2）檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，並設置：dj=min[dj，dk+lkj]，其中，lkj是從點k到j的直接連接距離。
（3）選取下一個點。從所有未標記的結點中，選取dj中最小的一個i：di=min[dj，所有未標記的點j]，點i就被選為最短路徑中的一點，並設為已標記的。
（4）找到點i的前一點。從已標記的點中找到直接連接到i的點j'，作為前一點，設置：pi= j'。
（5）如果所有點已標記，則算法完全退出，否則，記k=k ∪{i}，轉到（2）再繼續。
1.2 Dijkstra算法的分析與待改進的地方
其中節點1為起始點。根據上一節描述的Dijkstra算法，其中“◎”表示已標記的節點，“●”表示與已標記節點相鄰的未標記節點。可以看到。
從中可以觀察kMax和mMax，和之間的關係。
所有數據的起點相同，終點隨機選取；kMax、mMax為計算最短路徑時集合K和集合M中元素曾經達到的的最大數目，和則是集合K和集合M中元素的平均個數；ArcNum為起點到終點沿最短路徑所經過的弧段的個數；Distance是起點到終點的實際距離，單位是m。顯然，弧段的個數與實際距離不成正比。
關於表2的幾點說明：取表1的最後一組數據，即kMax=135，mMax=6 756來驗證一次Dijkstra算法計算最短路徑時集合K中元素個數Knum和集合M中元素個數Mnum之間的關係，Knum的采樣間隔大約為10。隨著計算的進行，集合K中元素的數目逐漸增多，集合M中元素的數目增長的非常快。若幹次計算後，集合K、M中的元素數目分別達到最大值kMax和mMax。
觀察表1、表2的數據，可以得到如下結論：
（1）隨著起點和終點間距離的增大，kMax、mMax和、都增大，但kMax增長速度遠小於mMax，增長速度遠小於。最壞情況下與的比例隻有3%左右。
（2）集合K中元素的數目始終小於集合M中元素的數目。因此，如果算法中我們隻針對集合K進行操作，將極大縮小d的規模，使修改d的時間和在d中選擇最小分量的時間因d的規模的縮小而降低很多。更進一步，如果d是有序的，則從k（k≤kMax）個有序數中選擇一個最小數的時間複雜度為O（1），而從m（m≤mMax）個未排序數中選擇一個最小數的時間複雜度為O（m）。可見，改進算法中集合K應是有序的。