周忠玉　方歡　方賢文

摘要：關(guān)于圖論最短路徑算法的圖形化演示程序的開(kāi)發(fā)和系統(tǒng)的設(shè)計(jì)。這里首先介紹最短路徑問(wèn)題的概念和最短路徑的算法（指迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法）。然后，在Eclipse和JDK1.6環(huán)境下開(kāi)發(fā)演示最短路徑問(wèn)題算法的流程。最后，運(yùn)行系統(tǒng)演示程序進(jìn)行正確性驗(yàn)證。該算法演示程序簡(jiǎn)單易用、清晰明了、形象而生動(dòng)的演示了算法。

關(guān)鍵詞：圖論；最短路徑；Dijkstra；Floyd；演示系統(tǒng)

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）18-0159-02

圖論問(wèn)題始終滲透整個(gè)計(jì)算機(jī)科學(xué)，可以說(shuō)每個(gè)編程者都不可避免地與圖打交道，因而圖論算法對(duì)計(jì)算機(jī)科學(xué)至關(guān)重要。它的應(yīng)用領(lǐng)域非常多。例如，圖論可以應(yīng)用于電路網(wǎng)絡(luò)分析、運(yùn)籌學(xué)、網(wǎng)絡(luò)、信息論、控制論以及計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域。我們知道最短路徑問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最為廣泛的問(wèn)題之一。而這里介紹的最短路徑算法是圖論算法中重要的一支。最短路徑算法可以解決許多問(wèn)題，例如：線路安排、管道鋪設(shè)、路由選擇、地址選擇、設(shè)備更新、廣場(chǎng)布局、時(shí)變拓?fù)渚W(wǎng)絡(luò)等。我們這里研究的就是最短路徑問(wèn)題的算法，具體指的是迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。這里通過(guò)開(kāi)發(fā)一個(gè)系統(tǒng)演示程序來(lái)生動(dòng)的闡述迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。該系統(tǒng)演示程序簡(jiǎn)單易用、清晰明了、界面友好、非常實(shí)用。該系統(tǒng)演示程序是在Eclipse和JDK1.6的環(huán)境下用java語(yǔ)言開(kāi)發(fā)而成的。它為解決最短路徑問(wèn)題提供了一個(gè)簡(jiǎn)單實(shí)用的平臺(tái)。

1 最短路徑問(wèn)題

定義：我們給定一個(gè)帶權(quán)重的有向圖G=（V，E）和權(quán)重函數(shù)w：E→R，該權(quán)重函數(shù)將每條邊映射到實(shí)數(shù)值的權(quán)重上。圖中一條路徑p=的權(quán)重w（p）是構(gòu)成該路徑的所有邊的權(quán)重之和：w（p）=∑w（vi-1 ， vi） ，i=1，2，3…，k。

假設(shè)一條從節(jié)點(diǎn)m到節(jié)點(diǎn)n的最短路徑權(quán)重為W（m，n），且W（m，n）計(jì)算如下：

①如果存在一條從節(jié)點(diǎn)m到節(jié)點(diǎn)n的路徑，則：W（m，n）=min{w（p）|p是一條從節(jié)點(diǎn)m到節(jié)點(diǎn)n的路徑}；②否則，W（m，n）=∞。

從節(jié)點(diǎn)m到節(jié)點(diǎn)n的路徑p，如果滿足w（p）= W（m，n）則該路徑p即為從節(jié)點(diǎn)m到節(jié)點(diǎn)n的最短路徑。求從節(jié)點(diǎn)m到節(jié)點(diǎn)n的最短路徑和最短距離的問(wèn)題就是最短路徑問(wèn)題。

2 最短路徑算法

2.1弗洛伊德算法思想

我們使用三重for循環(huán)產(chǎn)生一個(gè)矩陣來(lái)記錄每個(gè)節(jié)點(diǎn)間的最小距離。對(duì)于弗洛伊德（Floyd）算法我們使用矩陣Juzhen[i][j]（i，j=1，2，……n+1）存儲(chǔ)有向圖的權(quán)重值。所以，其基本思想為：初始化一個(gè)n階矩陣A（k），其主對(duì)角線上的元素初始化為0，非對(duì)角線上的元素初始化A（k） [i][j]，其中每一個(gè)A（k） [i][j]是節(jié)點(diǎn)i到節(jié)點(diǎn)j的權(quán)重值，k是運(yùn)算到第幾步。算法一開(kāi)始，我們選擇任意兩個(gè)節(jié)點(diǎn)分別作為起始點(diǎn)和終止點(diǎn)，若他們之間有邊則取其權(quán)重值作為他們的路徑長(zhǎng)度，若無(wú)權(quán)重邊，則令其路徑長(zhǎng)度為∞，再有k=0時(shí)，我們初始化A（k）[i][j]，此時(shí)A（0）[i][j]=Juzhen[i][j]，將路徑上的節(jié)點(diǎn)加入集合S中，之后再選擇不在集合S中但能構(gòu)成最短路徑的節(jié)點(diǎn)，使其加入集合S，如果在i節(jié)點(diǎn)和j節(jié)點(diǎn)之間增加了中間節(jié)點(diǎn)后，使得節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑比A（k） [i][j]小，就用新的權(quán)重值去更新A（k） [i][j]。

因此，弗洛伊德（Floyd）算法步驟如下：

（1）當(dāng)k=0時(shí)，A（0）[i][j]= Juzhen[i][j]； 其中Juzhen[i][j]為鄰接矩陣

（2）當(dāng)k=i+1，i+2，…，j時(shí)，A（k）[i][j]=min{A（k-1） [i][j]，A（k-1） [i][k]+A（k-1） [k][j]}

其中A（k）[i][j]表示節(jié)點(diǎn)點(diǎn)vi 到vj ， 中間節(jié)點(diǎn)的不大于k的最短路徑的長(zhǎng)度，這里求的是中間節(jié)點(diǎn)的不大于n的最短路徑的長(zhǎng)度即A（n）[i][j]。

因而，其算法可以描述為：

（1）令D[i][j]=A[i][j]

（2）for（k=1；k<=n；k++）

for（i=1；i<=n；i++）

for（j=1；j<=n；j++）

if（D[i][j]> D[i][k]+ D[k][j]）

{D[i][j]=D[i][k]+ D[k][j]}

（3）算法結(jié)束后矩陣D存儲(chǔ)了所有節(jié)點(diǎn)之間的最短路徑值。

2.2 迪杰斯特拉算法的思想

Dijkstra算法解決的是帶權(quán)重的有向圖上單源點(diǎn)最短路徑的問(wèn)題。該算法要求所有邊的權(quán)重都為非負(fù)值。Dijkstra算法把圖中所有的節(jié)點(diǎn)分為兩組：設(shè)集合S表示已經(jīng)求出的最短路徑上的節(jié)點(diǎn)的集合；集合T=V-S表示在集合V中而在節(jié)點(diǎn)S之外的所有的節(jié)點(diǎn)的集合。然后把集合T中節(jié)點(diǎn)按權(quán)值非減的次序排序，并按此順序依次加入到集合S里。除此之外，還要滿足如下兩個(gè)條件：第一，從出發(fā)點(diǎn)v0到集合S中每一個(gè)節(jié)點(diǎn)的最短路徑長(zhǎng)度A（k）[i][j]都應(yīng)該小于或者等于從節(jié)點(diǎn)v0到集合T中所有節(jié)點(diǎn)的權(quán)重值也即最短路徑長(zhǎng)度；第二，集合S和集合T都對(duì)應(yīng)一個(gè)距離值。S中的節(jié)點(diǎn)表示的距離是從出發(fā)點(diǎn)v0到該集合中每一個(gè)節(jié)點(diǎn)的最短路徑長(zhǎng)度，集合T中的節(jié)點(diǎn)表示從出發(fā)點(diǎn)v0到集合T中所有的節(jié)點(diǎn)且只經(jīng)過(guò)集合S中節(jié)點(diǎn)作為中間節(jié)點(diǎn)的最短路徑長(zhǎng)度。因此，迪杰斯特拉算法可描述為：

設(shè)置輔助數(shù)組dist，其中每個(gè)分量dist[k] 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑。

（1）S = {v0}；//頂點(diǎn)v0為源點(diǎn)

（2）設(shè)置集合V-S中各頂點(diǎn)的初始距離值；

（3）while （集合S中頂點(diǎn)數(shù)

{在集合V-S中選擇距離最小的頂點(diǎn)vj；S=S+{vj}；

調(diào)整集合VS中頂點(diǎn)的距離值；}

3 最短路徑算法圖形化演示程序檢驗(yàn)

下面通過(guò)一個(gè)實(shí)例檢驗(yàn)系統(tǒng)演示程序的正確性。

實(shí)例：如圖1所示，求一條從節(jié)點(diǎn)A到節(jié)點(diǎn)C的最短路徑，并求出其權(quán)重值。

具體操作步驟是：①運(yùn)行系統(tǒng)；②點(diǎn)擊新結(jié)點(diǎn)按鈕和結(jié)點(diǎn)連線按鈕，然后在畫(huà)布上用鼠標(biāo)點(diǎn)擊構(gòu)造結(jié)點(diǎn)和連線；③雙擊結(jié)點(diǎn)輸入結(jié)點(diǎn)名，雙擊連線輸入權(quán)重值，以此構(gòu)造出圖1；④選擇始點(diǎn)為A，終點(diǎn)為B，選擇使用的算法（迪杰斯特拉算法或弗洛伊德算法）；⑤點(diǎn)擊激活按鈕后，點(diǎn)擊開(kāi)始按鈕，結(jié)果如圖2所示；⑥點(diǎn)擊算法展示按鈕會(huì)出現(xiàn)迪杰斯特拉算法和弗洛伊德算法的展示選擇界面；⑦點(diǎn)擊概念展示按鈕會(huì)出現(xiàn)迪杰斯特拉算法和弗洛伊德算法的概念選擇界面；⑧在算法展示界面和概念展示界面點(diǎn)擊相應(yīng)的按鈕會(huì)彈出與此相符的PPT文件進(jìn)行展示。

4 結(jié)論

在了解圖論最短路徑的問(wèn)題的算法（迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法）、概念和原理的基礎(chǔ)上，開(kāi)發(fā)了一個(gè)算法圖形化演示程序，并對(duì)改程序進(jìn)行了正確性的驗(yàn)證。這里開(kāi)發(fā)的算法系統(tǒng)演示程序生動(dòng)形象地闡述了迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法的概念和原理，并通過(guò)畫(huà)圖的方式簡(jiǎn)化了操作。該系統(tǒng)演示程序簡(jiǎn)單易用、清晰明了、界面友好、非常實(shí)用。它為解決最短路徑問(wèn)題提供了一個(gè)簡(jiǎn)單實(shí)用的平臺(tái)，這樣的研究是有積極意義的。

參考文獻(xiàn)：

[1] 田豐，馬仲蕃.圖與網(wǎng)絡(luò)流理論[M].北京：科學(xué)出版社，1987.

[2] 徐鳳生.求最短路徑的新算法[J].計(jì)算機(jī)工程與科學(xué)，2006，2.

[3] 魏文紅，李清霞，蔡昭權(quán).一種基于桶結(jié)構(gòu)的單源最短路徑算法[J].計(jì)算機(jī)工程與科學(xué)，2012，4（34）：77-81

[4] 王樹(shù)西，吳政學(xué).改進(jìn)的Dijkstra 最短路徑算法及其應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，2012，5（39）：223-228

[5] 朱福喜.面向?qū)ο笈cJava程序設(shè)計(jì)[M]. 北京：清華大學(xué)出版社，2008.

[6] 朱福喜.Java編程技巧與開(kāi)發(fā)實(shí)例[M]. 北京：清華大學(xué)出版生，2004.

[7] 王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法[M]. 北京：中國(guó)鐵道出版社，2006.

[8] 侯風(fēng)巍.數(shù)據(jù)結(jié)構(gòu)要點(diǎn)精細(xì)[M]. 北京：北京航空航天大學(xué)出版社，2006.

[9] 劉萬(wàn)軍.Java程序設(shè)計(jì)實(shí)踐教程[M]. 北京：清華大學(xué)出版社， 2006.

[10] 方賢文.Java語(yǔ)言程序設(shè)計(jì)[M]. 安徽：安徽科學(xué)技術(shù)出版社，2014.

[11] 李興華.java開(kāi)發(fā)實(shí)戰(zhàn)經(jīng)典[M]. 北京：清華大學(xué)出版社，2009.

[12] 李剛.瘋狂java講義[M]. 北京：電子工業(yè)出版社，2012.

[13] 李鐘尉.Java從入門(mén)到精通[M]. 北京：清華大學(xué)出版社，2008.