java floyd算法求解最短路徑問題(完整程序代碼)

1、交通運輸學(xué)院課程設(shè)計引言在圖論中經(jīng)常會遇到這樣的問題，在一個有向圖里求出任意兩個節(jié)點之間的最短距離。當(dāng)節(jié)點之間的權(quán)值是正值的時候，我們可以采用Dijkstra算法，用貪心策略加于解決。但當(dāng)節(jié)點之間的權(quán)值有負(fù)數(shù)的時候，Dijkstra就行不通了，這里介紹另外一種算法Floyd最短路徑算法。對于任意圖，選擇存儲結(jié)構(gòu)存儲圖并實現(xiàn)FLOYD算法求解最短路經(jīng)。將問題分解，分解為兩方面。一是對于任意圖的存儲問題，第二個是實現(xiàn)FLOYD算法求解最短路經(jīng)。首先對于圖的創(chuàng)建選擇合適的存儲結(jié)構(gòu)進(jìn)行存儲，對于合適的存儲結(jié)構(gòu)可以簡化程序。本實驗采用鄰接矩陣存儲。然后是實現(xiàn)FLOYD算法求解最短路經(jīng)，在FLOYD算法中

2、路徑的長度即是圖中兩定點間邊的權(quán)值，F(xiàn)LOYD算法要求輸出任意兩個頂點間的最短路徑，而且經(jīng)過的頂點也要輸出?？紤]到問題的特殊性，采用一個二維數(shù)組和一個三維數(shù)組進(jìn)行存儲。二維數(shù)組存儲最短路徑，三維數(shù)組存儲路徑經(jīng)過的頂點，在進(jìn)行適當(dāng)?shù)乃惴ê髮@兩個數(shù)組進(jìn)行輸出即可。通過問題的分解，逐個解決，事先所要求的程序。最短路徑算法問題是計算機(jī)科學(xué)、運籌學(xué)、地理信息系統(tǒng)和交通誘導(dǎo)、導(dǎo)航系統(tǒng)等領(lǐng)域研究的一個熱點。傳統(tǒng)的最短路徑算法主要有Floyd算法和Dijkstra算法。Floyd算法用于計算所有結(jié)點之間的最短路徑。Dijkstra算法則用于計算一個結(jié)點到其他所有結(jié)點的最短路徑。Dijkstra算法是已經(jīng)證明

3、的能得出最短路徑的最優(yōu)解，但它的效率是一個很大的問題。對于具有n個結(jié)點的一個圖，計算一個結(jié)點到圖中其余結(jié)點最短路徑的算法時間復(fù)雜度為O(n2)。對于一座大中型城市，地理結(jié)點數(shù)目可能達(dá)到幾萬個到幾十萬個，計算最短路徑的時間開銷將是非常巨大的。本文根據(jù)吳一民老師的建議，分析當(dāng)前存在的各種求最短路徑的算法，提出一種新的基于層次圖的最短路徑算法，即將一個平面圖劃分若干子圖，子圖抽象為一個高層圖。最短路徑的計算首先在高層圖中進(jìn)行，縮小了最短路徑的查找范圍，降低了最短路徑計算的時間開銷。由于可以動態(tài)計算子圖間的阻抗函數(shù)，算法可適用于動態(tài)交通誘導(dǎo)系統(tǒng)。設(shè)計目的（1）培養(yǎng)學(xué)生分析解決問題的能力，掌握java語

4、言的程序設(shè)計方法；（2）通過課程設(shè)計實踐，訓(xùn)練并提高學(xué)生在統(tǒng)籌全局、結(jié)構(gòu)設(shè)計、查閱設(shè)計資料和計算機(jī)編程方面的能力；（3）提高學(xué)生實踐論文撰寫能力。任務(wù)與要求： (1) 理論設(shè)計部分以課程設(shè)計論文的形式提交，格式必須按照課程設(shè)計論文標(biāo)準(zhǔn)格式進(jìn)行書寫和裝訂；(2) 課程設(shè)計報告（論文）包括要求的作業(yè)。第一章 Floyd算法1.1 最短路的定義最短路徑問題是圖論研究中的一個經(jīng)典算法，旨在尋找圖中兩結(jié)點之間的最短路徑。算法的具體形式包括：確定起點的最短路徑問題即已知起始結(jié)點，求最短路徑問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路經(jīng)反轉(zhuǎn)的確定起點的問題。確定起點終點的最

5、短路徑問題即已知起點和終點求兩結(jié)點之間的最短路徑。求距離最短路徑問題求圖中所有的最短路徑。用于解決最短路徑問題的算法被稱為最短路徑算法。單源最短路 定義：給定一個賦權(quán)有向圖G =（V,E）,記G中每一條弧aij=(vi,vj)上的權(quán)為W(aij)=Wij,有給定G中的一個起點s和重點t，設(shè)p是G中從s到t的一條路，則定義路徑p的權(quán)是p中有弧的權(quán)之和，記為W（p），即:W（p）=又若p*是圖G中從s到t的一條路徑，且滿足W（p*）=minW（p）|p為Vs到Vt的路試中對G的所有從s到t的路p取最小，則稱p*為從s到t的最短路，W（p*）為s到t的最短距離。在一個圖G中，求從s到t的最短路徑和最

6、短距離問題就稱為最短路徑問題。1.2 Floyd的定義與思想 1.2.1 Floyd算法的定義 Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。 1.2.2 Floyd 算法的思想利用一個三重循環(huán)產(chǎn)生一個存儲每個結(jié)點最短距離的矩陣.弗洛伊德算法仍然使用圖的鄰接矩陣arcsn+1n+1來存儲帶權(quán)有向圖。算法的基本思想是:設(shè)置一個n x n的矩陣A(k)，其中除對角線的元素都等于0外，其它元素a(k)ij表示頂點i到頂點j的路徑長度，K表示運算步驟。開始時，以任意兩個頂點之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為，當(dāng)K=0時, A (0)i

7、j=arcsij，以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：   第一步，讓所有邊上加入中間頂點1，取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1)，第二步，讓所有邊上加入中間頂點2，取Aij與Ai2+A2j中較小的值，完成后得到A(2)，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果,A(n)ij表示頂點i到頂點j的最短距離。因此，弗洛伊德算法可以描述為:      

8、; A(0)ij=arcsij;               /arcs為圖的鄰接矩陣       A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj其中 k=1,2,n定義一個n階方陣序列：           D(-1), D(0), , D(n-1). &

9、#160; 其中 D(-1) ij = G.arcsij；             D(k) ij = min D(k-1)ij，D(k-1)ik + D(k-1)kj , k = 0,1, n-1    D(0) ij是從頂點vi 到vj , 中間頂點是v0的最短路徑的長度,       D(k) ij是從頂點vi 到vj , 中間頂點的序號不大于k的最短路徑長度,    D(n-1)ij是從頂

10、點vi 到vj 的最短路徑長度。1.3 Floyd算法描述 通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。a) 初始化：Du,v=Au,v b) For k:=1 to n For i:=1 to n For j:=1 to n If Di,j>Di,k+Dk,j Then DI,j:=DI,k+Dk,j; c) 算法結(jié)束：D即為所有點對的最短路徑矩陣 從圖的帶權(quán)鄰接矩陣A=a(i,j) n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(

11、n)的i行j 列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同 還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。 采用的是松弛技術(shù)，對在i和j之間的所有其他點進(jìn)行一次松弛。所以時間復(fù)雜度為O(n3); 其狀態(tài)轉(zhuǎn)移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,jmapi,j表示i到j(luò)的最短距離 K是窮舉i,j的斷點 mapn,n初值應(yīng)該為0，或者按照題目意思來做。當(dāng)然，如果這條路沒有通的話，還必須特殊處理,比如沒有mapi,k這條路 1.4 Floyd算法過程在圖論中經(jīng)常會遇到這樣的問題，在一個有向圖里，求出任意兩個節(jié)點之間的最短距離。我

12、們在離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)課上都遇到過這個問題，在計算機(jī)網(wǎng)絡(luò)里介紹網(wǎng)絡(luò)層的時候好像也遇到過這個問題，記不請了. 但是書本上一律采取的是Dijkstra算法，通過Dijkstra算法可以求出單源最短路徑，然后逐個節(jié)點利用Dijkstra算法就可以了。不過在這里想換換口味，采取Robert Floyd提出的算法來解決這個問題。下面讓我們先把問題稍微的形式化一下： 如果有一個矩陣D=d(ij)，其中d(ij)>0表示i城市到j(luò)城市的距離。若i與j之間無路可通，那么d(ij)就是無窮大。又有d(ii)=0。編寫一個程序，通過這個距離矩陣D，把任意兩個城市之間的最短與其行徑的路徑找出來。我們可以將問題

13、分解，先找出最短的距離，然后在考慮如何找出對應(yīng)的行進(jìn)路線。如何找出最短路徑呢，這里還是用到動態(tài)規(guī)劃的知識，對于任何一個城市而言，i到j(luò)的最短距離不外乎存在經(jīng)過i與j之間的k和不經(jīng)過k兩種可能，所以可以令k=1，2，3，.，n(n是城市的數(shù)目)，在檢查d(ij)與d(ik)+d(kj)的值；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j(luò)的最短距離，因此d(ik)+d(kj)就是i到j(luò)經(jīng)過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過k再到j(luò)的距離要比原來的i到j(luò)距離短，自然把i到j(luò)的d(ij)重寫為d(ik)+d(kj)，每當(dāng)一個k查完了，d

14、(ij)就是目前的i到j(luò)的最短距離。重復(fù)這一過程，最后當(dāng)查完所有的k時，d(ij)里面存放的就是i到j(luò)之間的最短距離了。所以我們就可以用三個for循環(huán)把問題搞定了，但是有一個問題需要注意，那就是for循環(huán)的嵌套的順序：我們可能隨手就會寫出這樣的程序，但是仔細(xì)考慮的話，會發(fā)現(xiàn)是有問題 for(int i=0; i<n; i+) for(int j=0; j<n; j+) for(int k=0; k<n; k+) 問題出在我們太早的把i-k-j的距離確定下來了，假設(shè)一旦找到了i-p-j最短的距離后，i到j(luò)就相當(dāng)處理完了，以后不會在改變了，一旦以后有使i到j(luò)的更短的距離時也不能再

15、去更新了，所以結(jié)果一定是不對的。所以應(yīng)當(dāng)象下面一樣來寫程序： for(int k=0; k<n; k+) for(int i=0; i<n; i+) for(int j=0; j<n; j+) 這樣作的意義在于固定了k，把所有i到j(luò)而經(jīng)過k的距離找出來，然后象開頭所提到的那樣進(jìn)行比較和重寫，因為k是在最外層的，所以會把所有的i到j(luò)都處理完后，才會移動到下一個k，這樣就不會有問題了，把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達(dá)，則Gi,j=d，d表示該路的長度；否則Gi,j=空值。 定義一個矩陣D用來記錄所插入點的信息，Di,j表示從Vi到Vj需要經(jīng)過的點，初始化Di,j

16、=j。 把各個頂點插入圖中，比較插點后的距離與原來的距離，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值變小，則Di,j=k。 在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為V5,V3,V1，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。 1.5 Floyd算法優(yōu)缺點分析Floyd算法適用于APSP(All Pairs Shortest Paths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此

17、算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次DijkStra算法。 優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單； 缺點：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。第二章 鄰接矩陣2.1 鄰接矩陣的定義鄰接矩陣（Adjacency Matrix）：是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個圖，其中V=v1,v2,vn。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣：2.2 鄰接矩陣的特點無向圖的鄰接矩陣一定是對稱的，而有向圖的鄰接矩陣不一定對稱。因此，用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n2個單元來存儲鄰接矩陣；對有n個頂點的無向圖則只存

18、入上（下）三角陣中剔除了左上右下對角線上的0元素后剩余的元素，故只需1+2+.+(n-1)=n(n-1)/2個單元。 無向圖鄰接矩陣的第i行（或第i列）非零元素的個數(shù)正好是第i個頂點的度。有向圖鄰接矩陣中第i行非零元素的個數(shù)為第i個頂點的出度，第i列非零元素的個數(shù)為第i個頂點的入度，第i個頂點的度為第i行與第i列非零元素個數(shù)之和。 用鄰接矩陣表示圖，很容易確定圖中任意兩個頂點是否有邊相連。 2.3 鄰接矩陣的表示方法2.3.1 圖的鄰接矩陣表示法 在圖的鄰接矩陣表示法中： 用鄰接矩陣表示頂點間的相鄰關(guān)系 用一個順序表來存儲頂點信息 2.3.2 圖的鄰接矩陣(Adacency Matrix) 設(shè)

19、G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣： Ai,j=1 若（Vi,Vj）或者<Vi,Vj>是E(G)中的邊； Ai,j=0 若（Vi,Vj）或者<Vi,Vj>不是E(G)中的邊。若G是網(wǎng)絡(luò)，則鄰接矩陣可定義為： Ai,j=Wij 若（Vi,Vj）或<Vi,Vj>屬于E（G） AI,j=0或 若（Vi,Vj）或<Vi,Vj>不屬于E（G） 其中： Wij 表示邊上的權(quán)值; 表示一個計算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。 【例】下面帶權(quán)圖的兩種鄰接矩陣分別為A 3 和A 4 。 2.3.3鄰接矩陣的特點：無向圖的鄰接矩

20、陣一定是一個對稱矩陣。無向圖的鄰接矩陣的第i行（或第i列）非零元素（或非無窮元素）個數(shù)為第i個頂點的度D（vi）.有向圖的鄰接矩陣的第i行非零元素（或非無窮元素）個數(shù)為第i個頂點的度OD(vi)，第i列非零元素（或非無窮元素）個數(shù)就是第i個頂點的入度ID（vi）。鄰接矩陣表示圖，很容易確定圖中任意兩個頂點之間是否有邊相連。容易判斷兩個頂點之間是否有長度為m的路徑相連。鄰接矩陣表示法的缺點：鄰接矩陣占用的存儲單元個數(shù)只與圖中的結(jié)點個數(shù)有關(guān)，而與邊的數(shù)目無關(guān)。一個n各節(jié)點的圖，若其邊數(shù)比n平方少得多，那么鄰接矩陣中存在大量的無用的單元。第三章 Floyd算法實例 3.1 Floyd算法實

21、例現(xiàn)有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關(guān)系，邊上的權(quán)代表城市之間的距離。求每個城市的最短距離【輸入】 用V表示各個城市，輸入頂點Vi與Vj，【輸出】 輸出所有可能連接的城市的最短距離。最短路徑算法的作用就是在圖中找出任意兩點間最短距離的途徑，比如可以在地圖上找出任兩個城市之間路程最短的那條路徑。有兩種算法可以實現(xiàn)，一種是迪杰斯特拉（Dijkstra）算法，一種是弗洛伊德（Floyd）算法。弗洛伊德（Floyd）算法過程：、用Dvw記錄每一對頂點的最短距離。、依次掃描每一個點，并以其為基點再遍歷所有每一對頂點D的值，看看是否可用過該基點讓這對頂點間的距離更小。算法理解：

22、最短距離有三種情況：、兩點的直達(dá)距離最短。（如下圖<v,x>）、兩點間只通過一個中間點而距離最短。（圖<v,u>）、兩點間用通過兩各以上的頂點而距離最短。（圖<v,w>）對于第一種情況：在初始化的時候就已經(jīng)找出來了且以后也不會更改到。對于第二種情況：弗洛伊德算法的基本操作就是對于每一對頂點，遍歷所有其它頂點，看看可否通過這一個頂點讓這對頂點距離更短，也就是遍歷了圖中所有的三角形（算法中對同一個三角形掃描了九次，原則上只用掃描三次即可，但要加入判斷，效率更低）。對于第三種情況：如下圖的五邊形，可先找一點（比如x，使<v,u>=2），就變成了四邊形問

23、題，再找一點（比如y,使<u,w>=2），可變成三角形問題了（v,u,w），也就變成第二種情況了，由此對于n邊形也可以一步步轉(zhuǎn)化成四邊形三角形問題。（這里面不用擔(dān)心哪個點要先找哪個點要后找，因為找了任一個點都可以使其變成（n1）邊形的問題）。第四章 結(jié)論通過Floyd算法求解圖中頂點的最短路徑問題實驗，更加深入的了解了數(shù)據(jù)結(jié)構(gòu)與算法在各個領(lǐng)域的應(yīng)用。比如圖的最短路徑問題，衍生為校內(nèi)導(dǎo)游圖，乘客路徑問題等等的實際性的日常問題。在該實驗的求解過程中，把問題分解為三個部分來解決。首先考慮的是對于任意圖的存儲問題。在數(shù)據(jù)結(jié)構(gòu)與算法中，介紹了多種圖的存儲結(jié)構(gòu)，有鄰接矩陣存儲，鄰接表存儲以及十

24、字鏈表等等存儲方法。考慮到本實驗要對圖進(jìn)行求解路徑，采用鄰接矩陣存儲。鄰接矩陣存儲圖很容易判斷圖中兩個頂點是否相連。例如，判斷Vi和Vj是否相連，只需檢查Gij是否等于零，如果該、等于零則不相連。以上是兩個頂點是否直接相連的算法。然后是路徑問題，對于任意兩個頂點，路徑也就分為三個情況，即直接相連是最短路徑，經(jīng)過某幾個頂點后，經(jīng)過的路徑是最短路徑，還有這兩個頂點之間沒有最短路徑。對于直接相連的路徑就是最短路徑，直接輸出即可。例如a>b直接相連，且最短路徑就是直接路徑，路徑長度為10，輸出a到b的路徑就為：a>b，路徑長度為10。經(jīng)過某幾個定點后的路徑是最短路徑，用二維數(shù)組length

25、先保存最短路徑長。若lengthij>lengthik+lengthkj則經(jīng)過k點后i到j(luò)得的路徑短一些，此時將lengthik+lengthkj賦值給lengthij，用二維數(shù)組path記錄下經(jīng)過的點k，這樣在循環(huán)里對整個路徑都進(jìn)行一邊比較，保存下最短路徑以及這些路徑經(jīng)過的頂點。對于兩點之間沒有路徑的問題，lengthij一直為最大值，若有路徑則同第二步，沒有則lengthij一直保持不變。最后待解決的問題就是輸出任意兩點之間的最短路徑，從i到j(luò)的最短路徑全部保存在length中，要向輸出任意兩點之間的最短路徑長度并不難，但如何輸出之間經(jīng)歷過的定點呢?在存入的時候首先存入p是離j最近的

26、一點，然后是離p最近的一點，依次存入，最后一個存入的是離i最近的頂點，所以輸出的時候必須倒序輸出。采用向前遞歸算法實現(xiàn)。在3x3循環(huán)里，如果lengthij=0或者lengthij=INF（INF是自定義的最大值）都是沒有路徑的，lengthij=0此時若i=j，則是定點無路徑。若lengthij=INF則i到j(luò)沒有路徑。如果lengthij=0但是i!=j，此時說明i到j(luò)的最短路徑是0，路徑是存在的，應(yīng)該另外考慮這種情況，同下面的輸出一致。若以上三種情況都不符合則執(zhí)行正常的輸出操作，輸出從i到j(luò)經(jīng)過的頂點，并輸出路徑長度。通過上述三個步驟，解決了Floyd算法的最短路徑問題。參考文獻(xiàn)1 朱福

27、喜編著.面向?qū)ο笈cJava程序設(shè)計.北京：清華大學(xué)出版社，20082 焦永蘭主編.管理運籌學(xué).北京：中國鐵道出版社，20023 黃國瑜，葉乃菁編著。數(shù)據(jù)結(jié)構(gòu)。清華大學(xué)出版社，20054 朱福喜，唐曉軍編著.Java編程技巧與開發(fā)實例.北京：清華大學(xué)出版生，20045 王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京:中國鐵道出版社，2006.56 侯風(fēng)巍，楊永田.數(shù)據(jù)結(jié)構(gòu)要點精細(xì).北京航空航天大學(xué)出版社，2006.8附錄1 程序流程圖：2 程序?qū)崿F(xiàn)代碼：package Example; import java.awt.*; import java.awt.event.*; import java.awt.g

28、eom.Ellipse2D; import javax.swing.*; public class testpaint extends JFrame implements ActionListener int length = null; public void Floyd(int G) int max =9999; int row = G.length; / 圖G的行數(shù) int A = new introwrow;/ 定義任意兩點之間經(jīng)過的點 intPath = new introw;/ 記錄一條路徑 length = new introwrow; for (int i = 0; i <

29、; row; i+) / 處理圖兩點之間的路徑 for (int j = 0; j < row; j+) if (Gij = 0) Gij = max; / 沒有路徑的兩個點之間的路徑為默認(rèn)最大 if (i = j) Gij = 0; / 本身的路徑長度為0 for (int i = 0; i < row; i+) / 初始化為任意兩點之間沒有路徑 for (int j = 0; j < row; j+) Aij = -1; for (int i = 0; i < row; i+) Pathi = -1; / 假設(shè)任意兩點之間的沒有路徑 for (int m = 0;

30、m < row; +m) for (int n = 0; n < row; +n) lengthmn = Gmn; for (int u = 0; u < row; +u) for (int m = 0; m < row; +m) for (int n = 0; n < row; +n) if (lengthmn > lengthmu + lengthun) lengthmn = lengthmu + lengthun;/ 如果存在更短路徑則取更短路徑 Amn = u;/ 把經(jīng)過的點加入 for (int i = 0; i < row; i+) / 求

31、出所有的路徑 int point = new int1; for (int j = 0; j < row; j+) point0 = 0; Pathpoint0+ = i; outputPath(A, i, j, Path, point); void outputPath(intA, int i, int j, intPath, int point) / 輸出i到j(luò)的路徑的實際代碼,point記錄一條路徑的長度 if (i = j) return; if (Aij = -1) Pathpoint0+ = j; else outputPath(A, i, Aij, Path, point)

32、; outputPath(A, Aij, j, Path, point); int shuzu=new int66; Button button=new Button("計算"); Label label1 = new Label("從頂點"); Label label2 = new Label("到頂點"); Label label3 = new Label("的最短距離是"); TextField text1 = new TextField(""); TextField text2 = ne

33、w TextField(""); TextField text3 = new TextField("");public testpaint()super("Floyd最短路算法："); text3.addActionListener(this); text1.setColumns(0); /設(shè)置text1的大小 text2.setColumns(0); /設(shè)置text2的大小 text3.setColumns(0); /設(shè)置text3的大小 button.addActionListener(this); setLayout(new F

34、lowLayout(); add(label1); add(text1); add(label2); add(text2); add(label3); add(text3); add(button); pack(); setSize(380,266); setVisible(true); int data = /鄰接矩陣 0,3,5,8,9999, 3,0,6,4,11, 5,6,0,2,9999, 8,4,2,0,10, 9999,11,9999,10,0,; for (int i = 0; i < data.length; i+) for (int j = i; j < dat

35、a.length; j+) if (dataij != dataji) return; Floyd Test=new Floyd(data); for (int i = 0; i < data.length; i+) for (int j = i; j < datai.length; j+) System.out.println("從頂點"+"V"+(i+1)+"到頂點"+"V"+(j+1)+"的最短路是:"+Test.lengthij); System.out .println()

36、;shuzuij=Test.lengthij; public void actionPerformed(ActionEvent e) int a=Integer.parseInt(text1.getText(); int b=Integer.parseInt(text2.getText();text3.setText(String.valueOf(shuzua-1b-1); public void paint(Graphics g) super.paint(g); Graphics2D g1 = (Graphics2D)g; /Ellipse2D.Double /public Ellipse2D.Double(double x,double y,double w,double h) / 根據(jù)指定坐標(biāo)構(gòu)造和初始化 Ellipse2D 參數(shù)： /x - 窗體矩形左上角的 X 坐標(biāo),y - 窗體矩形左上角的 Y 坐標(biāo),