交通運輸學院課程設計

1、<p><b>　　目 錄</b></p><p>　　第1章 引 言2</p><p><b>　　1.1目的：2</b></p><p><b>　　1.2 內容：2</b></p><p>　　1.3主要任務：2</p><p>

2、;　　第2章 設計過程3</p><p><b>　　2.1設計思路3</b></p><p>　　2.1.1Floyd算法3</p><p>　　2.1.2鄰接矩陣3</p><p>　　2.1.3圖形用戶界面4</p><p>　　2.2設計內容及分析4</p>&

3、lt;p>　　2.2.1 算法部分4</p><p>　　2.2.2圖形界面處理部分：9</p><p>　　第3章 總 結13</p><p><b>　　附 錄14</b></p><p><b>　　參考文獻17</b></p><p><b>

4、;　　第1章 引 言</b></p><p><b>　　1.1目的：</b></p><p>　　發(fā)現(xiàn)課程學習中的不足和薄弱環(huán)節(jié)，予以補充和加強。綜合運用在課程學習過程中所學知識，同時為了實現(xiàn)課程設計的規(guī)定成果進行更深入的理論學習和實踐拓展。培養(yǎng)獨立思考和解決問題的能力，探索和創(chuàng)新的能力。具體如下：</p><p>　　⑴復習、

5、鞏固Java語言的基礎知識，進一步加深對Java語言的理解和掌握；</p><p>　　⑵課程設計為學生提供了一個既動手又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結合起來，鍛煉學生的分析解決實際問題的能力。提高學生適應實際，實踐編程的能力；</p><p>　?、峭ㄟ^課程設計實踐，訓練并提高學生在查閱設計資料、運用標準與規(guī)范和應用計算機等方面的能力。</p>&l

6、t;p><b>　　1.2 內容：</b></p><p>　　求解最短路問題（Floyd算法）；</p><p>　　功能要求：實現(xiàn)Floyd算法，求解最短路問題，用GUI界面實現(xiàn)。</p><p><b>　　1.3主要任務：</b></p><p>　　在java開發(fā)環(huán)境下，運用GUI用

7、戶界面技術，通過Floyd算法，實驗對最短路問題的求解。要求通過對Floyd算法的學習，掌握其原理，運用Java語言來實現(xiàn)該算法流程，取得最短路方案。通過GUI界面顯示該最短路問題的網(wǎng)絡圖，并標記顯示出最短路的路徑。</p><p><b>　　第2章 設計過程</b></p><p><b>　　2.1設計思路</b></p>

8、<p>　　2.1.1Floyd算法</p><p>　　首先：對最短路問題中的Floyd算法有個較為深入的了解。其基本思想可簡歸納如下：floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。首先我們的目標是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，floyd算法為這個目標重新做一個詮釋。假設Ak(i,j)表示從i到j中途不經(jīng)過索引比k大的點的最短路徑。它將最短路徑的概念做了限制，使得該限制有機會滿足迭代關

9、系，這個迭代關系就在于研究：假設Ak(i,j)已知，是否可以借此推導出Ak-1(i,j)。經(jīng)過分析，可得到最短路的關鍵式子： Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) )，這是由Java實現(xiàn)Floyd算法的基本依據(jù)。簡單說，依次掃描每一點(k)，并以該點作為中介點，計算出通過k點的其他任意兩點(i,j)的最短距離，這就是floyd算法的精髓。&

10、lt;/p><p>　　具體做法：利用一個三重循環(huán)產(chǎn)生一個存儲每個結點最短距離的矩陣.弗洛伊德算法仍然使用圖的鄰接矩陣arcs[n+1][n+1]來存儲帶權有向圖。算法的基本思想是:設置一個n x n的矩陣A(k)，其中除對角線的元素都等于0外，其它元素a(k)[i][j]表示頂點i到頂點j的路徑長度，K表示運算步驟。開始時，以任意兩個頂點之間的有向邊的權值作為路徑長度，沒有有向邊時，路徑長度為∞，當K=0時, A

11、(0)[i][j]=arcs[i][j]，以后逐步嘗試在原路徑中加入其它頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。簡單概括為：   </p><p>　　第一步，讓所有邊上加入中間頂點1，取A[i][j]與A[i][1]+A[1][j]中較小的值作A[i][j]的值，完成后得到A(1)，</p><p>

12、;　　第二步，讓所有邊上加入中間頂點2，取A[i][j]與A[i][2]+A[2][j]中較小的值，完成后得到A(2)…，如此進行下去，當?shù)趎步完成后，得到A(n)，A(n)即為我們所求結果,A(n)[i][j]表示頂點i到頂點j的最短距離。</p><p><b>　　2.1.2鄰接矩陣</b></p><p>　　在設計過程中，還會涉及一個重要概念：鄰接矩陣。在圖

13、的鄰接矩陣表示法中： </p><p>　?、?用鄰接矩陣表示頂點間的相鄰關系 </p><p>　?、?用一個順序表來存儲頂點信息</p><p>　　若G是網(wǎng)絡，則鄰接矩陣可定義為： </p><p><b>　　其中： </b></p><p>　　w ij 表示邊上的權值; </p&

14、gt;<p>　　∞表示一個計算機允許的、大于所有邊上權值的數(shù)。</p><p>　　【例】下面帶權圖的兩種鄰接矩陣分別為A 3 和A 4 。 </p><p>　　2.1.3圖形用戶界面</p><p>　　為了達到最終目的，又對Java中的圖形用戶界面做了簡單的學習，認識到Java 不僅僅用于網(wǎng)絡開發(fā)，也可以開發(fā)應用程序。這就體現(xiàn)的GUI的作用所在

15、。在學習了窗口的應用后，又對Graphics類，做了較多的學習。用于繪制圖形和簡單的圖像處理，比如后面用到的畫直線，畫圓等.</p><p>　　最后，經(jīng)過多次調試，將Floyd算法與GUI界面結合起來，達到最終目的，即通過運用Java實現(xiàn)由圖形用戶界面顯示Floyd算法。</p><p>　　2.2設計內容及分析</p><p>　　2.2.1 算法部分</

16、p><p><b>　　聲明部分：</b></p><p>　　public class Floyd {</p><p>　　int[][] length ;// 任意兩點之間路徑長度 </p><p>　　int[][][] path ;// 任意兩點之間的路徑</p><p>　　public F

17、loyd(int[][] G) { </p><p>　　int MAX = 100; </p><p>　　int row = G.length;// 圖G的行數(shù) </p><p>　　int[][] spot = new int[row][row];// 定義任意兩點之間經(jīng)過的點 </p><p>　　int[] onePath = ne

18、w int[row];// 記錄一條路徑 </p><p>　　length = new int[row][row]; </p><p>　　path = new int[row][row][]; </p><p><b>　　對路徑的處理部分：</b></p><p>　　for (int i = 0; i <

19、row; i++) // 處理圖兩點之間的路徑 </p><p>　　for (int j = 0; j < row; j++) { </p><p>　　if (G[i][j] == 0) </p><p>　　G[i][j] = MAX;// 沒有路徑的兩個點之間的路徑為默認最大 </p><p>　　if (i == j) <

20、;/p><p>　　G[i][j] = 0;// 本身的路徑長度為0 </p><p><b>　　} </b></p><p>　　for (int i = 0; i < row; i++) // 初始化為任意兩點之間沒有路徑 </p><p>　　for (int j = 0; j < row; j++) &

21、lt;/p><p>　　spot[i][j] = -1; </p><p>　　for (int i = 0; i < row; i++) // 假設任意兩點之間的沒有路徑 </p><p>　　onePath[i] = -1; </p><p>　　找最短路的過程部分：</p><p>　　for (int v

22、= 0; v < row; ++v) </p><p>　　for (int w = 0; w < row; ++w) </p><p>　　length[v][w] = G[v][w]; </p><p>　　for (int u = 0; u < row; ++u) </p><p>　　for (int v = 0;

23、v < row; ++v) </p><p>　　for (int w = 0; w < row; ++w) </p><p>　　if (length[v][w] > length[v][u] + length[u][w]) { </p><p>　　length[v][w] = length[v][u] + length[u][w];// 如果

24、存在更短路徑則取更短路徑 </p><p>　　spot[v][w] = u;// 把經(jīng)過的點加入 </p><p><b>　　} </b></p><p>　　for (int i = 0; i < row; i++) { // 求出所有的路徑 </p><p>　　int[] point = new int

25、[1]; </p><p>　　for (int j = 0; j < row; j++) { </p><p>　　point[0] = 0; </p><p>　　onePath[point[0]++] = i; </p><p>　　outputPath(spot, i, j, onePath, point); </p>

26、;<p>　　path[i][j] = new int[point[0]]; </p><p>　　for (int s = 0; s < point[0]; s++) </p><p>　　path[i][j][s] = onePath[s]; </p><p><b>　　} </b></p><p&

27、gt;<b>　　記錄最短路部分：</b></p><p>　　void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point) {</p><p>　　// 輸出i到j 的路徑的實際代碼,point[]記錄一條路徑的長度 </p><p>　　if (i == j)

28、 </p><p><b>　　return; </b></p><p>　　if (spot[i][j] == -1) </p><p>　　onePath[point[0]++] = j; </p><p><b>　　else { </b></p><p>

29、;　　outputPath(spot, i, spot[i][j], onePath, point); </p><p>　　outputPath(spot, spot[i][j], j, onePath, point); </p><p><b>　　} </b></p><p><b>　　} </b></p&g

30、t;<p><b>　　主函數(shù)部分：</b></p><p>　　public static void main(String[] args) {</p><p>　　System.out.println("請輸入所求問題的中間節(jié)點數(shù)：");</p><p><b>　　int row;</b&

31、gt;</p><p>　　Scanner shuru=new Scanner(System.in);</p><p>　　row=shuru.nextInt();</p><p>　　System.out.println("請依次輸入兩節(jié)點間的距離：");</p><p><b>　　int n,m;</

32、b></p><p>　　int data[][]=new int[row][row];</p><p>　　for(m=0;m<row;m++){</p><p>　　for(n=0;n<row;n++){</p><p>　　data[m][n]=shuru.nextInt();</p><p>

33、<b>　　}</b></p><p><b>　　}</b></p><p>　　System.out.println("原矩陣為：");</p><p>　　for(int i=0;i<row;i++){</p><p>　　for(int j=0;j<row;j

34、++){</p><p>　　System.out.printf("%4d",data[i][j]);</p><p><b>　　}</b></p><p>　　System.out.println();</p><p><b>　　}</b></p><p

35、>　　對輸入數(shù)據(jù)進行處理：</p><p>　　for (int i = 0; i < data.length; i++)</p><p>　　for (int j = i; j < data.length; j++)</p><p>　　if (data[i][j] != data[j][i]) </p><p><

36、b>　　return; </b></p><p><b>　　}</b></p><p>　　Floyd test=new Floyd(data); </p><p>　　for (int i = 0; i < data.length; i++) </p><p>　　for (int j = i

37、; j < data[i].length; j++) { </p><p>　　System.out.println(); </p><p>　　System.out.print("從v"+i+"到v"+j+"所經(jīng)過的點有: "); </p><p><b>　　//輸出經(jīng)過的路點</

38、b></p><p>　　for (int k = 0; k < test.path[i][j].length; k++) </p><p>　　System.out.print(test.path[i][j][k] + " "); </p><p>　　System.out.println(); </p><p&

39、gt;　　System.out.println("從v"+i+"到v"+j+"最短路徑長度是:" </p><p>　　+ test.length[i][j]);// 輸出最短路部分</p><p><b>　　} </b></p><p><b>　　} </b>

40、;</p><p><b>　　}</b></p><p>　　部分截圖如圖1，圖2：</p><p><b>　　圖1</b></p><p><b>　　圖2</b></p><p>　　2.2.2圖形界面處理部分：</p><p

41、><b>　　外層窗體 ：</b></p><p>　　public static void main(String args[]){</p><p>　　ComputerFrame fr=new ComputerFrame();</p><p>　　fr.setTitle("Floyd算法求最短路問題"); <

42、/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　class ComputerFrame extends JFrame implements TextListener</p><p>　　{ TextArea text1,text2;</p>

43、;<p>　　public ComputerFrame(){</p><p>　　setLayout(new FlowLayout());</p><p>　　text1=new TextArea(10,30);//確定文本區(qū)的大小</p><p>　　text2=new TextArea(10,30);</p><p>　　a

44、dd(text1);</p><p>　　add(text2); </p><p>　　text2.setEditable(false);</p><p>　　text1.addTextListener(this);</p><p>　　setSize(300,400);</p><p>　　setVisible(tr

45、ue);</p><p>　　addWindowListener(new WindowAdapter(){</p><p>　　public void windowClosing(WindowEvent e){</p><p>　　System.exit(0);</p><p><b>　　} </b></p>

46、;<p><b>　　});</b></p><p>　　validate();</p><p><b>　　}</b></p><p>　　生成如圖3的一個兩個文本框的窗體。上面用來輸入數(shù)據(jù)，下面用來顯示路徑圖；</p><p><b>　　圖3</b><

47、/p><p><b>　　內部畫圖部分：</b></p><p>　　public void actionPerformed(ActionEvent e){</p><p>　　int a=Integer.parseInt(text1.getText());</p><p>　　int b=Integer.parseInt(

48、text2.getText());</p><p>　　text3.setText(String.valueOf(shuzu[a-1][b-1]));</p><p><b>　　}</b></p><p>　　public void paint(Graphics g){ </p><p>　　super.paint(g

49、); </p><p>　　Graphics2D g1 = (Graphics2D)g;</p><p>　　//Ellipse2D.Double </p><p>　　//public Ellipse2D.Double(double x,double y,double w,double h)</p><p>　　// 根據(jù)指定坐標構造和初始

50、化 Ellipse2D 參數(shù)：</p><p>　　Ellipse2D e1 = new Ellipse2D.Double(40,60 ,20,20); </p><p>　　Ellipse2D e2 = new Ellipse2D.Double(200,60,20,20); </p><p>　　Ellipse2D e3 = new Ellipse2D.Doubl

51、e(200,200,20,20); </p><p>　　Ellipse2D e4 = new Ellipse2D.Double(40,200,20,20); </p><p>　　Ellipse2D e5 = new Ellipse2D.Double(320,130,20,20); </p><p>　　Ellipse2D e6 = new Ellipse2D.D

52、ouble(400,220,20,20); </p><p>　　//x - 窗體矩形左上角的 X 坐標,y - 窗體矩形左上角的 Y 坐標,w - 窗體矩形的寬度,h - 窗體矩形的高度</p><p>　　g1.setPaint(Color.RED); </p><p>　　g1.draw(e1); </p><p>　　g1.drawS

53、tring("V1", 45, 75);</p><p>　　g1.draw(e2); </p><p>　　g1.drawString("V2", 205,75);</p><p>　　g1.draw(e3);</p><p>　　g1.drawString("V3", 45, 2

54、15);</p><p>　　g1.draw(e4);</p><p>　　g1.drawString("V4", 205, 215);</p><p>　　g1.draw(e5); </p><p>　　g1.drawString("V5", 325, 145);</p><p&g

55、t;　　g1.draw(e6); </p><p>　　g1.drawString("V6", 400, 180);</p><p>　　g1.drawLine(60, 70, 200,70);</p><p>　　g1.drawString("3", 130, 70);</p><p>　　g1.dr

56、awLine(50, 80, 50, 200);</p><p>　　g1.drawString("5", 40, 135);</p><p>　　g1.drawLine(60, 210,200 ,210);</p><p>　　g1.drawString("2", 130,210);</p><p>

57、　　g1.drawLine(210, 80, 210,200);</p><p>　　g1.drawString("4", 200, 135);</p><p>　　g1.drawLine(55, 75, 203, 203);</p><p>　　g1.drawString("8", 110, 120);</p>

58、<p>　　g1.drawLine(55, 203, 203, 75);</p><p>　　g1.drawString("6", 85, 170);</p><p>　　g1.drawLine(220, 70, 320, 140);</p><p>　　g1.drawString("11", 280,110);&

59、lt;/p><p>　　g1.drawLine(220, 210,320, 140);</p><p>　　g1.drawString("10", 280, 160);</p><p><b>　　} </b></p><p><b>　　}</b></p><p

60、><b>　　第3章 總 結</b></p><p>　　通過本次課程設計，基本上解決了Floyd算法求解最短路徑問題，這使我更加深入的了解了Java語言對于實際應用的意義。更主要的是，我深深的意識到，我對圖形用戶界面有關方面知識的嚴重匱乏，對它的學習有十分的必要性。尤其是在這次課程設計中，并沒有對圖形用戶界面有很好的應用，沒能對Floyd算法完全由GUI來實現(xiàn)，沒能完全符合老師的要求

61、，還希望老師能夠見諒。這一點也正是我尚待解決的重要問題。</p><p><b>　　附 錄</b></p><p>　　package floyd;</p><p>　　public class Floyd_0 {</p><p>　　int[][] length = null;</p><p&g

62、t;　　int[][][] path = null; </p><p>　　public Floyd_0 (int[][] G) { </p><p>　　int MAX = 100; </p><p>　　int row = G.length; </p><p>　　int[][] spot = new int[row][row];int

63、[] onePath = new int[row]; </p><p>　　length = new int[row][row]; </p><p>　　path = new int[row][row][]; </p><p>　　for (int i = 0; i < row; i++) </p><p>　　for (int j =

64、 0; j < row; j++) { </p><p>　　if (G[i][j] == 0) </p><p>　　G[i][j] = MAX;if (i == j) </p><p>　　G[i][j] = 0; } </p><p>　　for (int i = 0; i < row; i++) </p&g

65、t;<p>　　for (int j = 0; j < row; j++)</p><p>　　spot[i][j] = -1; </p><p>　　for (int i = 0; i < row; i++) </p><p>　　onePath[i] = -1; </p><p>　　for (int v = 0

66、; v < row; ++v) </p><p>　　for (int w = 0; w < row; ++w) </p><p>　　length[v][w] = G[v][w]; </p><p>　　for (int u = 0; u < row; ++u) </p><p>　　for (int v = 0; v &

67、lt; row; ++v) </p><p>　　for (int w = 0; w < row; ++w) </p><p>　　if (length[v][w] > length[v][u] + length[u][w]) { </p><p>　　length[v][w] = length[v][u] + length[u][w];更短路徑 <

68、;/p><p>　　spot[v][w] = u; </p><p><b>　　} </b></p><p>　　for (int i = 0; i < row; i++) { </p><p>　　int[] point = new int[1]; </p><p>　　for (int j

69、 = 0; j < row; j++) { </p><p>　　point[0] = 0; </p><p>　　onePath[point[0]++] = i; </p><p>　　outputPath(spot, i, j, onePath, point); </p><p>　　path[i][j] = new int[poi

70、nt[0]]; </p><p>　　for (int s = 0; s < point[0]; s++) </p><p>　　path[i][j][s] = onePath[s]; </p><p><b>　　} </b></p><p><b>　　} </b></p>

71、<p><b>　　} </b></p><p>　　void outputPath(int[][] spot, int i, int j, int[] onePath, int[] point{ </p><p>　　if (i == j) </p><p><b>　　return; </b></p&g

72、t;<p>　　if (spot[i][j] == -1) </p><p>　　onePath[point[0]++] = j; </p><p><b>　　else { </b></p><p>　　outputPath(spot, i, spot[i][j], onePath, point); </p>&l

73、t;p>　　outputPath(spot, spot[i][j], j, onePath, point); </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　public static void main(String[] args) {</p>

74、<p>　　System.out.println("請輸入所求問題的中間節(jié)點數(shù)：");</p><p><b>　　int row;</b></p><p>　　Scanner shuru=new Scanner(System.in);</p><p>　　row=shuru.nextInt();</p&g

75、t;<p>　　System.out.println("請依次輸入兩節(jié)點間的距離：");</p><p><b>　　int n,m;</b></p><p>　　int data[][]=new int[row][row];</p><p>　　for(m=0;m<row;m++){</p>

76、<p>　　for(n=0;n<row;n++){</p><p>　　data[m][n]=shuru.nextInt();</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　System.out.println("輸