Maple實現(xiàn)基于Dijkstra算法的最短路徑

夏磊

【摘要】Dijkstra算法是從一個頂點到其余各頂點的最短路徑算法，用來解決有向圖中最短路徑問題，本人運用永久和臨時標記的方式，結(jié)合數(shù)學軟件maple中圖論程序包networks，解決最短路徑問題。

【關鍵詞】Dijkstra算法 最短路徑 maple

【中圖分類號】G64 【文獻標識碼】A 【文章編號】2095-3089（2017）45-0174-02

一、引言

隨之智能手機的高度發(fā)展，手機導航已成為有車一族出行必備的工具之一，如何在繁雜的城市道路中找到一條最短、行車最快的路徑能夠快速到達目的地，是人們非常關心的問題之一。

實際上，很多問題都可以歸結(jié)為一個賦權(quán)圖的最短路徑問題。賦權(quán)圖的最短路徑問題可表述為：設賦權(quán)連通圖G=（V，E，W），其中V為頂點集，E為邊集，W為權(quán)（可以是道路長度，修路費用等），在所有頂點vi到頂點vj的路徑中，尋找一條長度最短的路徑，即一條路徑的長度等于路徑中所有邊的權(quán)值之和。

二、Dijkstra算法

1959年荷蘭計算科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）給出了一個世界上公認最好的計算最短路徑的方法，它是對每個頂點做標記，令L（v）代表頂點v的標記，在求解過程中，有些標記被記為臨時標記，其余的被記為永久標記。令T表示當前標記為臨時標記的頂點集合，算法開始時，所有標記都被標記為永久標記，在每次的迭代過程中，算法將一個頂點的標記從臨時標記更改為永久標記。舉例來說，假設有A，B，C，D，E，F(xiàn)六個地點，其拓撲結(jié)構(gòu)如圖1所示，欲找出A到D的最短路徑。

由于這個問題規(guī)模比較小，用窮舉法可以很容易知道最短路徑為A→E→C→D，長度為9。

在Dijkstra算法中，如果L（v）是頂點v的永久標記，那么L（v）就是從起點到v的最短路徑的長度。要在一個連通的賦權(quán)圖中尋找頂點A到D的最短路徑長度，邊（i， j）的權(quán)值w（i， j）>0，且頂點x的標記為L（x），此時Dijkstra算法可詳細描述為：

1.L（a）=0；for 所有頂點 x≠a do L（x）=∞

2.令T為所有頂點組成的集合

3.while z∈T do

4.begin

5.從T中找出最有最小L（v）的頂點v

6.T： T- {v}

7.for 所有與v相鄰的頂點 x∈T do L（x）：min{L（x），L（v）+w（v， x）}

8.end

9.end.

下面求圖1由頂點A到D（即D到A）的最短路徑及其長度：依次執(zhí)行到算法第五行（此時圖的狀態(tài)如圖2①），此時T為所有頂點，其中具有零時標記的頂點為D（為了區(qū)分頂點是否已被考察過，考察過的頂點我們用方塊表示），修改T為{C，F(xiàn)，B，E，A}，更新與D相鄰的頂點C，F(xiàn)的標記L（C）=min{∞，0+3}=3，L（F）=min{∞，0+7}=7，并標注頂點C，F(xiàn)，此時圖的狀態(tài)如圖2②，其中標注“D，3”表明它的長度和它從D被標注的事實。接下來，在T中找標記L（x）的最小頂點C（把頂點C圖形改為方塊），并更新與C相鄰的頂點B，E的標注，參見圖2③，重復上述步驟，找出L（x）的最小頂點E（改為方塊），并更新頂點E，B的標注（參見圖2④）。接著該改頂點E為方塊，并更新頂點A的標注（參見圖2⑤），這時，就要改A為方塊，因A已經(jīng)做了永久標記，故算法結(jié)束，所有由D到A的最短路徑長度為9，從A開始順著標注返回可以得到最短路徑為A→E→C→D。

三、maple實現(xiàn)

圖論是應用數(shù)學和離散數(shù)學的重要組成部分之一，maple軟件作為一種計算機代數(shù)系統(tǒng)，通過20多年的不斷發(fā)展，已經(jīng)成為當今世界上最優(yōu)秀的數(shù)學軟件之一，其中包含的圖論程序包networks，對于研究圖論和圖論的教學提供了一個強有力的工具。Networks提供了非常豐富的函數(shù)，在繪制簡單圖及進行Dijkstra算法時，我們需要用到一下函數(shù)：

在使用networks中的命令之前，需裝載該程序包，即執(zhí)行with（networks），首先畫出圖1的簡單圖（圖3），命令如下：

>with（networks）：

new（G）：

addvertex（{A， B， C， D， E， F}， G）：

addedge（[{A， B}， {A， E}， {B， C}， {B， F}， {E， F}， {E， C}， {C， D}， {F， D}]， weight=[4， 5， 3， 6， 8， 1， 3， 7]， G）：

>draw（G）；

然后找出圖中邊的長度：

>eweight（G）；

table（[e13=8，e2=5，e12=6，e1=4，e9=4，e14=1，e4=6，e7=3， e16=7， e8=7， e11=3， e15=3， e6=1， e5=8， e3=3， e10=5]）

使用maple提供的shortpathtree（G， v）命令（使用Dijkstra算法）求解最短路徑問題，并找出最短路徑（圖4）：

> T：=shortpathtree（G， A， W）：

>draw（T）；

最后利用vweight（v， G）命令得到A到D的最短路徑長度為9。

>vweight（D， T）；

四、結(jié)論

進入二十一世紀，隨著多媒體技術和數(shù)學軟件的迅速發(fā)展，計算機代數(shù)系統(tǒng)maple能夠處理圖論等數(shù)學分支，這是它優(yōu)于其他數(shù)學軟件的特點之一，利用maple軟件進行圖的構(gòu)建，幫助人們解決最短路徑問題，進行圖論計算，理解圖論的概念和方法，提供了有效的手段。這種利用CAS（Computer Algebra System，計算機代數(shù)系統(tǒng)）進行數(shù)學研究的方式，在當前信息化快速發(fā)展的時代，值得提倡和推廣。

參考文獻：

[1]部亞松.VC++實現(xiàn)基于Dijkstra算法的最短路徑[J].科技信息.2008（18）.

[2]張小紅，張建勛.《數(shù)學軟件與數(shù)學實驗》[M].北京：清華大學出版社.2004.endprint