1.引言
交通誘導系統的乙個核心技術是最優路徑的選擇技術。根據交通網路模型中各頂點和頂點之間的長度、時間或費用等屬性權值，通過dijkstra最短路徑演算法，解決有向圖即交通網路模型中源點到其他頂點的最短路徑問題。
2.建立交信道路網路模型
交信道路網是路徑誘導的基礎和物件，首先需要建立交信道路網路模型。交信道路網中的路段具有屬性，且同一路段的兩個方向其屬性一般不完全相同，有向圖能夠很好地表達實際的交通網路，便於處理同路段兩個方向的不同屬性和單行線、交叉口轉向限制等特殊交通屬性。綜上，採用帶權有向圖來表達交信道路網。
其中，道路的終點和十字路口通常定義為乙個頂點，兩個頂點之間的道路定義為一條弧，每條弧根據其距離、途中所需時間或交通費用等定義為路段權值。在有向圖上，一條以i為起點，以j為終點的路徑是一些頂點的序列，其中前一條弧的終點是後一條弧的起點，一條路線用乙個有序的點集描述，而一條路線的長度、時間或者費用等屬性為這條路徑上的所有弧的權值之和。這樣便建立好了交信道路網路的模型。
3.最短路徑演算法
迪傑斯特拉（dijkstra）演算法是經典路徑誘導規劃演算法，dijkstra演算法是乙個按路徑長度遞增的次序產生最短路徑的演算法，演算法比較簡單，容易實現，但計算量較大。
3.1演算法分析：首先引進輔助向量d，它的每個分量d[i]表示當前所找到的從始點v0到每個終點vi的最短路徑的長度。
為d[i]賦初值，若從v0到vi有弧，則d[i]為弧上的權值，否則置d[i]為∞。則長度為d[j]=min的路徑就是從v0出發的長度最短的一條最短路徑，此路徑為v0—vj。設下一條長度次短的路徑的終點是vk，則這條路徑或者是v0—vk，或者是v0—vj—vk。
它的長度是v0到vk弧上的權值或d[j]和vj到vk弧上權值之和。
3.2演算法正確性證明：設s為為已切得最短路徑的終點的集合，則有結論：
下一條最短路徑（設其終點為vx）或者是v0—vx，或者是中間只經過s中的頂點而最後到達頂點x的路徑。採用反證法證明如下：假設此路徑上有乙個頂點不在s中，則說明存在一條終點不在s而長度比此路徑短的路徑。
這是不可能的，因為dijkstra演算法是按路徑長度遞增的次序來產生各最短路徑的，弧長度比此路徑短的所有路徑均已產生，它們的終點必定在是中，故假設不成立，演算法正確可行。
3.3演算法描述：
設起始點為v0，頂點集為v，初始態vi∈v。
（1）用帶權鄰接矩陣arcs表示帶權有向圖，arcs[i][j]表示弧上的權值。若不存在，則置arcs[i][j]為∞。s為已找到從v0出發的
最短路徑的終點的集合，它的初始狀態為空集。從v0出發到圖上其餘各頂點（終點）vi可能達到的最短路徑長度的初值為：d[i]=arcs[0][i] vi∈v。
（2）選擇vj，使得d[j]=min，vj就是當前求得的一條從v 出發的最短路徑的終點，並令s=s∪。
（3）修改從v0出發到集合v-s上任一頂點vk可達的最短路徑長度。如果d[j]+arcs[j][k]（4）重複操作（2）、（3）共n-1次，由此求得從v0到圖上其餘各頂點的最短路徑是一次路徑長度遞增的序列。
3.4dijkstra 演算法的執行速度：dijkstra 演算法的最初的時間複雜度為o （v*v+e），源點可達的話，o（v*lgv+e*lgv）=>o（e*lgv），當是稀疏圖的情況時，e=v*v/lgv，演算法的時間複雜度可為o（v^2）。
用大o符號將dijkstra 演算法的執行時間表示為邊數 m 和頂點數 n 的函式。dijkstra 演算法最簡單的實現方法是用乙個鍊錶或者陣列來儲存所有頂點的集合 q，所以搜尋 q 中最小元素的運算（extract-min(q)）只需要線性搜尋 q 中的所有元素，這樣演算法的執行時間是 o(e^2)。
3.5dijkstra演算法實現：定義n為有向圖中的頂點個數，arcs[i][j].w為有向圖中頂點i到頂點j的權值。首先利用如下語句為鄰接矩陣賦初值，均為∞。
有向圖中，若vx到vy有弧利用下面語句依次輸入頂點號和弧上權值，並將權值賦給arcs[vx][vy].w。至此，交通網路模型即帶全有向圖建立完成。
輸入出發頂點v0 ，置已找到從v0出發的最短路徑的終點的集合s[n]初始狀態為空集。通過以下語句找到從v0出發的最短路徑的終點vj，使得
d[j]=min
上述語句中的條件語句if（find(s,i)!=1）是確保頂點vi在v-s中，find(s,i)函式的作用是若頂點vi在s中返回1，否則返回0。其**如下：
接下來需要對已寫入的最短路徑長度做修改，利用下面的語句完成如果
d[j]+arcs[j][k]是將已經求得終點放入集合s中。若有修改則v0到vj的路徑中間有若干頂點，若無修改則v0到vj的最短路徑就是v0—vj。
最後同過輸出語句輸出起始點v0到各個頂點的最短路徑的權值和路徑的頂點序列。若arcs[v0][i].w =infinity，則表示v0到vi無窮遠，無法到達。
3.6演算法實現：結合例項展示成果。
下圖為乙個帶權有向圖：
下圖顯示該有向圖中從v0到其餘各點的最短路徑：
程式執行結果：
輸出結果與預期結果相同，正確地實現了dijkstra最短路徑演算法。
參考文獻
嚴蔚敏，吳偉民.資料結構[m].北京：
清華大學出版社，1997.186-190. 徐士良.
實用資料結構[m].北京：清華大學出版社，2007.
133-139.
底園園，蘇小會.交通誘導系統中動態路徑誘導演算法的研究[j].計算機與數字工程，2011,39（2）：33-35.
鮑培明.距離尋優中dijkstra演算法的優化[j].計算機研究與發展，2001,38（3）：307-309.
最短路徑Dijkstra演算法實驗報告
class graph template void graph creat graph template void graph show shortestpath template void graph shortestpath dij d v0 0 final v0 true for i 1 i ...
最短路徑演算法 三種演算法簡介
dijkstra演算法，a 演算法和d 演算法 dijkstra演算法是典型最短路演算法，用於計算乙個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充套件，直到擴充套件到終點為止。dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。dijkstra...
最短路徑問題 專題
初中數學中最短路徑問題雖然只是乙個課題學習，但它在中學數學中的地位很重要，是大考 小考 競賽中經常涉及的乙個考點。所以我們要對它有足夠的重視。初中最短路徑問題主要針對軸對稱圖形考慮的。那麼只要涉及軸對稱圖形就有可能產生最短路徑問題。在此之前，我們接觸過的最短距離問題是 1 兩點間直線段最短 2 點到...