基于一般Dijkstra的改進算法在最短路徑問題中的應用

岳曉娟

[摘 要]首先，本文以一般Dijkstra算法為基礎，對一般Dijkstra算法的計算方式進行了改進；然后，通過具體算例將一般Dijkstra算法與其改進算法的具體步驟進行了詳細演示；最后，分析了基于一般Dijkstra算法的改進算法在教學過程中體現出的求解步驟更加快捷、方便，最小T標號尋找時間較短且出錯率較低，最短路徑尋找時間較短及圖示算法方便學生理解四方面的優點，期望對《運輸與配送》課程中關于最短運輸路線問題的教學具有一定的推廣意義。

[關鍵詞]最短路徑問題；Dijkstra算法；改進

[中圖分類號]O157.5 [文獻標識碼]A

Dijkstra算法作為典型的最短路徑算法，用于計算圖中一個頂點到其地各頂點的最短路徑。Dijkstra算法在物流專業課程《運輸與配送》中的最短運輸路線選擇這部分內容中也有涉及，且內容較為重要，但經過長期教學發現，大多數學生認為一般Dijkstra算法計算步驟較多，計算速度較慢，容易出錯，理解不深，難以掌握。因此，筆者改進了一般Dijkstra算法的呈現形式，嘗試了以圖示法來展示一般Dijkstra算法，更加方便學生理解與教師教學。

1 最短路徑問題的描述

對最短路線問題的描述：設G=（V，E）為帶權圖，V={v0，v1，…，vn-1}，E={e1，e2，…，em}，n個頂點，m條邊，圖中各邊（vi，vj）有權dij（dij=∞，表示vi，vj之間無邊），vi，vj為圖中任意兩點，單源最短路徑就是從G中找到源點v0到其余各點的最短路徑。

2 最短路徑問題的一般Dijkstra算法求解

目前Dijkstra標號法被認為是求無負權網絡最短路線問題的最好方法。算法的基本思路基于以下原理：若序列的最短路，則序列的最短路。即若{v0，v1，…，vn-1，vn}是從v0到vn的最短路線，則序列{v0，v1，…，vn-1}必為從v0到vn-1的最短路線。Dijkstra標號法的計算方法如下：

2.1 標號定義

定義兩種標號：T標號（臨時標號）和P標號（永久標號），給vi點一個P標號，表示從v0到vi點的最短路權，vi點的標號不再改變；給vi點一個T標號，表示v0到vi點的估計最短路權的上界，是一種臨時標號，凡沒有得到P標號的點都有T標號。算法：每一步都把某一點的T標號改為P標號，當終點vn-1得到P標號時，全部計算結束。

2.2 計算步驟

（1）給v0以P標號，P（v0）=0，其余各點均給T標號，T（vi）=+∞。

（2）若vi點為剛剛得到P標號的點，考慮這樣的點vj：（vi，vj）屬于E，且vj為T標號。對于vi的T標號進行如下的更改：

T（vj）=min[T（vj），P（vi）+dij]

（3）比較所有具有T標號的點，把最小者T標號改為P標號，即：

P（）=min[T（vi）]

當存在兩個以上最小者時，任取一個改為P標號。若終點得到P標號則計算結束，否則用代替vi轉回步驟（2）。

3 最短路徑問題的改進算法求解

考慮到一般Dijkstra算法求解過程中書寫內容過多，容易出錯，因此，在一般Dijkstra算法求解步驟的基礎上嘗試了對一般Dijkstra算法進行改進的圖示法。具體步驟如下：

（1）在第一行和第一列依次寫上v0，v1，…，vn-1；

（2）從起點v0開始，在第一行v0與第一列v0，交叉的空格內填寫0，代表P（v0）=0，并找出與v0直接相連的點vj，并設定T（vj）=d0j，第二行其余各空格均填寫+∞，代表T（vi）=+∞；

（3）從第二行中的數據中選擇數值最小的（假設最小值為min），并在對應的空格內記為，代表已經找到一條從起點v0出發到達最小數值對應第一列那一頂點（從最小數值垂直向上畫線，與第一行交叉的那個頂點）的最短路徑，即已將最小數值對應的點修改為P標號；

（4）從剛剛已經得到P標號的點（在數值右上角打了*號的該數值畫垂直線與第一行交叉的頂點）出發，找到與該點后續相連的點，并將這些點對應的空格數值進行如下標記：

T（vj）=min[T（vj），P（vi）+dij]

（5）比較所有頂點中未標*的點，給最小者（未標*的所有列中的數字取最小）標注*號；當存在兩個以上最小者時，任取一個標注為*號。若終點得到*號則計算結束，否則重復步驟（4）（5）。

4 兩種算法的算例比較分析

4.1 給出一個帶權圖G=（V，E），如圖1所示，請找出從起點v0出發到達終點v7的最短路線

4.4 對比分析

通過以上兩種方法的算例求解，很顯然，基于一般Dijkstra算法的改進算法在方便學生理解與教師教學方面呈現出了較多的優勢：

（1）一般Dijkstra算法求解步驟書寫較多，而改進算法的求解步驟書寫更加快捷、方便；

（2）一般Dijkstra算法求解過程中，每一步在尋找最小T標號數值時需在前面步驟中認真尋找T標號最小的數值，尋找時間較長，且若稍有疏忽極易出錯，而改進算法則只需在表中未打*號的列中的數字中選擇最小的即可。因此，其選擇最小T標號的時間較短，且出錯率較低；

（3）一般Dijkstra算法求解過程最后一步倒推最短路線時，需在求解步驟中認真尋找P標號，并將每一步的P標號進行倒推，然后得出最短路線。而改進算法只需從終點開始在表中找到每一步打*號的點，然后將其對應的右下角的角標作為前一個點，即可一次倒推出最短路線，其求解時間較短，且出錯率較低。

通過以上結論可得，基于一般Dijkstra算法的改進算法在最短路徑問題的求解過程中更加方便、快捷，不僅能夠使得學生便于理解，而且有助于教師教學。因此，其在《運輸與配送》課程中的最短運輸路線問題的求解過程中具有一定的推廣意義。

[參考文獻]

[1] 陳芳芳，姜忠義，吳春青.運籌學教學中的動態規劃求解最短路徑問題的一個注記[J].高師理科學刊，2016（09）.

[2] 徐天亮.運輸與配送（第2版）[M].北京：中國物資出版社，2012.