圖論最短路徑算法的圖形化演示及系統(tǒng)設(shè)計

周忠玉　方歡　方賢文

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

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

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）18-0159-02

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

1 最短路徑問題

定義：我們給定一個帶權(quán)重的有向圖G=（V，E）和權(quán)重函數(shù)w：E→R，該權(quán)重函數(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é)點m到節(jié)點n的最短路徑權(quán)重為W（m，n），且W（m，n）計算如下：

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

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

2 最短路徑算法

2.1弗洛伊德算法思想

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

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

（1）當k=0時，A（0）[i][j]= Juzhen[i][j]； 其中Juzhen[i][j]為鄰接矩陣

（2）當k=i+1，i+2，…，j時，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é)點點vi 到vj ， 中間節(jié)點的不大于k的最短路徑的長度，這里求的是中間節(jié)點的不大于n的最短路徑的長度即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存儲了所有節(jié)點之間的最短路徑值。

2.2 迪杰斯特拉算法的思想

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

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

（1）S = {v0}；//頂點v0為源點

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

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

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

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

3 最短路徑算法圖形化演示程序檢驗

下面通過一個實例檢驗系統(tǒng)演示程序的正確性。

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

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

4 結(jié)論

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

參考文獻：

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

[2] 徐鳳生.求最短路徑的新算法[J].計算機工程與科學，2006，2.

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

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

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

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

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

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

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

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

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

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

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