【正文】 he corresponding reasonable solution. Key words：traffic advisory shortest path Dijkstra algorithm Floyd algorithm1序 言最短路徑問題一直在計算機科學、交通工程學、地理信息系統(tǒng)、運籌學等學科中是一個研究的熱點，它不僅是資源分配問題解決的基礎，更是線路選擇問題解決的基礎，特別是在地圖、車輛調度以及路由選擇方面有著廣泛的應用。本文的其它部分組織如下：第一章概述了交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)的目的和意義、選題背景和技術線路。經典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結構及算法的有效結合使得新的最短路徑算法不斷涌現(xiàn)。當用斐波納契堆時，算法4時間復雜度為 O(M+N1ogN)。Dist 數(shù)組最終存放源點到各頂點的最短路徑結果。所以，我們假設 Dis(i,j)為節(jié)點 u 到節(jié)點 v 的最短路徑的距離，對于每一個節(jié)點 k，我們檢查 Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短，我們便設置 Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當我們遍歷完所有節(jié)點 k，Dis(i,j)中記錄的便是 i 到 j 的最短路徑的距離。目前常用的 Java 平臺基于 ，最近版本為 。系統(tǒng)的開放性和可擴充性：系統(tǒng)在開發(fā)過程中，應該充分考慮以后的可擴充性。private String dis = 。else {mGraph[i][j] = 32767。}}// 輸出鄰接矩陣public void showMGraph() {String s = 最短路徑的鄰接矩陣是(無向圖)：\n。// 存放線段頂點int i = 1。if (x || y) {lineList[i].setColor()。 k length。 y++) { if (table[1][y] 0)// 如果 y 相鄰于 1 (y, length(1, y))。// p 存放每對頂點之間的最短路徑for (i = 1。boolean c2Name = !circleList[j].()。// 存放路徑String lineString = 。return mGraphCopy。}public void changeFlag() {// 修改訪問狀態(tài)。}}}// 該點到頂尖 id 的 距離。(p)。}public static Point getTopointMin(ArrayListPoint arr, Point p) {Point temp = null。調查表明人們在出行時往往更傾向于轉車次數(shù)較少的路線，這樣便降低了人們的辦事效率。圖論[M].北京，北京理工大學出版社，1997. [5] 陸鋒。參 考 文 獻[1] 嚴蔚敏。交通咨詢現(xiàn)代化作為城市現(xiàn)代化的重要內容，首先應是城市居民的生活交通現(xiàn)代化，這是以人為本原則的基本含義和根本要求。Point p1 = getTopointMin(arr, (i))。 i sum。flag = false。BufferedReader bufr = new BufferedReader(new InputStreamReader())。 i 。} else {dis += ppath(i, j) + j + \n 路徑長度為: + D[i][j] + \n。 j++) {if (i == j)// 對角線上的元素（即頂點自身之間）不予考慮continue。 } }int i, j, k。// p 存放每對頂點之間的最短路徑for (i = 1。 j length。 lineList[i].yLocation == gv[j + 1]。}s = dis。//如果輸入的距離不能轉換成整形 默認距離是 1 }catch(Exception e) {m = 1。 i circleNum。（二）系統(tǒng)功能結構1. 系統(tǒng)構架設計首先總體的步驟是：迪克斯特拉算法的具體流程圖如下：13弗洛伊德算法的具體流程圖如下：14程序源代碼如下：//Floyd 算法public class ShortPathALG {private Drawing[] circleList = null。(2) 編譯成 .class 字節(jié)碼文件 byte code（一種二進制文件） 。在硬件或操作系統(tǒng)平臺上安裝一個 Java 平臺之后，Java 應用程序就可運行。FloydWarshall 算法的時間復雜度為 O(N3)，空間復雜度為 O(N2)。51959 年狄克斯特拉（Dijkstra）提出一個按路徑“長度”遞增的次序產生最短路徑的算法，即：把圖中所有的頂點分成兩組，第一組 S 包括已經確定最短路徑的頂點，初始時只含有源點；第二組 VS 中包括尚未包括最短路徑的頂點，初始時含有圖中初源點之外的所有其他頂點。鄰接表數(shù)據(jù)結構已被證明是網(wǎng)絡表達中最有效率的數(shù)據(jù)結構，在最短路徑算法中得到了廣泛應用。本題目的意義在于，用 java 軟件技術實現(xiàn)最短路徑算法在交通咨詢中的重要應用，對模擬結果進行分析討論，為將來能夠有效解決各大城市的交通問題提供可靠的依據(jù)。按照起點終點及路徑的數(shù)據(jù)和特征，最短路徑問題可分為五種類型：兩個節(jié)點間的最短路徑、所有節(jié)點的最短路徑、K則最短路徑、實時最短路徑和指定必經點的最短路徑問題。這樣的一個交通系統(tǒng)可以回答人們提出的有關交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構的學位或學歷而使用過的材料。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準用徒手畫3）畢業(yè)論文須用 A4 單面打印，論文 50 頁以上的雙面打印4）圖表應繪制于無格子的頁面上5）軟件工程類課題應有程序清單，并提供電子文檔1）設計（論文）2）附件：按照任務書、開題報告、外文譯文、譯文原文（復印件）次序裝訂IV目錄序 言 ...........................................................................................................1一、緒 論 ....................................................................................................2（一）課題的背景和意義 ..................................................................................................2（二）研究現(xiàn)狀 ..................................................................................................................2 ....................................................................................................................2 ............................................................................................................................3 ................................................................................................................................3（三）研究內容 ..................................................................................................................4（四）論文結構 ..................................................................................................................4二、最短路徑算法相關原理 ........................................................................4（一）DIJKSTRA 算法 .............................................................................................................4 ....................................................................................................................................5 ...........................................................................................................................................5 ...........................................................................................................................................5（二）FLOYD 算法 ................................................................................................................7： ................................................................................................................................8： ........................................................................................................................................8 算法過程矩陣的計算十字交叉法 .....................................................................................8三、開發(fā)工具與環(huán)境 ..................................................................................10（一）JAVA 技術 ................................................................................................................101. Java 簡介 .............................