基于一般Dijkstra的改進(jìn)算法在最短路徑問題中的應(yīng)用

岳曉娟

[摘 要]首先，本文以一般Dijkstra算法為基礎(chǔ)，對(duì)一般Dijkstra算法的計(jì)算方式進(jìn)行了改進(jìn)；然后，通過具體算例將一般Dijkstra算法與其改進(jìn)算法的具體步驟進(jìn)行了詳細(xì)演示；最后，分析了基于一般Dijkstra算法的改進(jìn)算法在教學(xué)過程中體現(xiàn)出的求解步驟更加快捷、方便，最小T標(biāo)號(hào)尋找時(shí)間較短且出錯(cuò)率較低，最短路徑尋找時(shí)間較短及圖示算法方便學(xué)生理解四方面的優(yōu)點(diǎn)，期望對(duì)《運(yùn)輸與配送》課程中關(guān)于最短運(yùn)輸路線問題的教學(xué)具有一定的推廣意義。

[關(guān)鍵詞]最短路徑問題；Dijkstra算法；改進(jìn)

[中圖分類號(hào)]O157.5 [文獻(xiàn)標(biāo)識(shí)碼]A

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

1 最短路徑問題的描述

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

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

目前Dijkstra標(biāo)號(hào)法被認(rèn)為是求無負(fù)權(quán)網(wǎng)絡(luò)最短路線問題的最好方法。算法的基本思路基于以下原理：若序列的最短路，則序列的最短路。即若{v0，v1，…，vn-1，vn}是從v0到vn的最短路線，則序列{v0，v1，…，vn-1}必為從v0到vn-1的最短路線。Dijkstra標(biāo)號(hào)法的計(jì)算方法如下：

2.1 標(biāo)號(hào)定義

定義兩種標(biāo)號(hào)：T標(biāo)號(hào)（臨時(shí)標(biāo)號(hào)）和P標(biāo)號(hào)（永久標(biāo)號(hào)），給vi點(diǎn)一個(gè)P標(biāo)號(hào)，表示從v0到vi點(diǎn)的最短路權(quán)，vi點(diǎn)的標(biāo)號(hào)不再改變；給vi點(diǎn)一個(gè)T標(biāo)號(hào)，表示v0到vi點(diǎn)的估計(jì)最短路權(quán)的上界，是一種臨時(shí)標(biāo)號(hào)，凡沒有得到P標(biāo)號(hào)的點(diǎn)都有T標(biāo)號(hào)。算法：每一步都把某一點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)，當(dāng)終點(diǎn)vn-1得到P標(biāo)號(hào)時(shí)，全部計(jì)算結(jié)束。

2.2 計(jì)算步驟

（1）給v0以P標(biāo)號(hào)，P（v0）=0，其余各點(diǎn)均給T標(biāo)號(hào)，T（vi）=+∞。

（2）若vi點(diǎn)為剛剛得到P標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn)vj：（vi，vj）屬于E，且vj為T標(biāo)號(hào)。對(duì)于vi的T標(biāo)號(hào)進(jìn)行如下的更改：

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

（3）比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者T標(biāo)號(hào)改為P標(biāo)號(hào)，即：

P（）=min[T（vi）]

當(dāng)存在兩個(gè)以上最小者時(shí)，任取一個(gè)改為P標(biāo)號(hào)。若終點(diǎn)得到P標(biāo)號(hào)則計(jì)算結(jié)束，否則用代替vi轉(zhuǎn)回步驟（2）。

3 最短路徑問題的改進(jìn)算法求解

考慮到一般Dijkstra算法求解過程中書寫內(nèi)容過多，容易出錯(cuò)，因此，在一般Dijkstra算法求解步驟的基礎(chǔ)上嘗試了對(duì)一般Dijkstra算法進(jìn)行改進(jìn)的圖示法。具體步驟如下：

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

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

（3）從第二行中的數(shù)據(jù)中選擇數(shù)值最小的（假設(shè)最小值為min），并在對(duì)應(yīng)的空格內(nèi)記為，代表已經(jīng)找到一條從起點(diǎn)v0出發(fā)到達(dá)最小數(shù)值對(duì)應(yīng)第一列那一頂點(diǎn)（從最小數(shù)值垂直向上畫線，與第一行交叉的那個(gè)頂點(diǎn)）的最短路徑，即已將最小數(shù)值對(duì)應(yīng)的點(diǎn)修改為P標(biāo)號(hào)；

（4）從剛剛已經(jīng)得到P標(biāo)號(hào)的點(diǎn)（在數(shù)值右上角打了*號(hào)的該數(shù)值畫垂直線與第一行交叉的頂點(diǎn)）出發(fā)，找到與該點(diǎn)后續(xù)相連的點(diǎn)，并將這些點(diǎn)對(duì)應(yīng)的空格數(shù)值進(jìn)行如下標(biāo)記：

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

（5）比較所有頂點(diǎn)中未標(biāo)*的點(diǎn)，給最小者（未標(biāo)*的所有列中的數(shù)字取最?。?biāo)注*號(hào)；當(dāng)存在兩個(gè)以上最小者時(shí)，任取一個(gè)標(biāo)注為*號(hào)。若終點(diǎn)得到*號(hào)則計(jì)算結(jié)束，否則重復(fù)步驟（4）（5）。

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

4.1 給出一個(gè)帶權(quán)圖G=（V，E），如圖1所示，請(qǐng)找出從起點(diǎn)v0出發(fā)到達(dá)終點(diǎn)v7的最短路線

4.4 對(duì)比分析

通過以上兩種方法的算例求解，很顯然，基于一般Dijkstra算法的改進(jìn)算法在方便學(xué)生理解與教師教學(xué)方面呈現(xiàn)出了較多的優(yōu)勢(shì)：

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

（2）一般Dijkstra算法求解過程中，每一步在尋找最小T標(biāo)號(hào)數(shù)值時(shí)需在前面步驟中認(rèn)真尋找T標(biāo)號(hào)最小的數(shù)值，尋找時(shí)間較長(zhǎng)，且若稍有疏忽極易出錯(cuò)，而改進(jìn)算法則只需在表中未打*號(hào)的列中的數(shù)字中選擇最小的即可。因此，其選擇最小T標(biāo)號(hào)的時(shí)間較短，且出錯(cuò)率較低；

（3）一般Dijkstra算法求解過程最后一步倒推最短路線時(shí)，需在求解步驟中認(rèn)真尋找P標(biāo)號(hào)，并將每一步的P標(biāo)號(hào)進(jìn)行倒推，然后得出最短路線。而改進(jìn)算法只需從終點(diǎn)開始在表中找到每一步打*號(hào)的點(diǎn)，然后將其對(duì)應(yīng)的右下角的角標(biāo)作為前一個(gè)點(diǎn)，即可一次倒推出最短路線，其求解時(shí)間較短，且出錯(cuò)率較低。

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

[參考文獻(xiàn)]

[1] 陳芳芳，姜忠義，吳春青.運(yùn)籌學(xué)教學(xué)中的動(dòng)態(tài)規(guī)劃求解最短路徑問題的一個(gè)注記[J].高師理科學(xué)刊，2016（09）.

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