【正文】 ..........................................................................................................11四、交通咨詢系統(tǒng)的實現(xiàn) ..........................................................................11（一）系統(tǒng)分析 ................................................................................................................11： ..........................................................................................................................11 ..............................................................................................................................12 ..................................................................................................................................12（二）系統(tǒng)功能結(jié)構(gòu) ........................................................................................................121. 系統(tǒng)構(gòu)架設(shè)計 ................................................................................................................................12 ..................................................................................................................................143. 測試數(shù)據(jù)及分析 ............................................................................................................................26五、設(shè)計總結(jié) .............................................................................................28V致謝 ............................................................................................................29參 考 文 獻 ...............................................................................................29交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)內(nèi) 容 摘 要目前在交通咨詢領(lǐng)域，最短路徑算法的研究和應(yīng)用越來越多，其中最短路徑算法的效率問題是普遍關(guān)注并且在實際應(yīng)用中迫切需要解決的問題。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標(biāo)明。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學(xué)位或?qū)W歷而使用過的材料。本人授權(quán)　　 　 　大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。這樣的一個交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個城市到其他城市的最短路徑，或者任意兩個城市之間的最短路徑問題。例如OPSF開放路由選擇協(xié)議，每一個OPSF路由器都維護一個描述自治系統(tǒng)范圍內(nèi)到每個目標(biāo)的最短路徑。按照起點終點及路徑的數(shù)據(jù)和特征，最短路徑問題可分為五種類型：兩個節(jié)點間的最短路徑、所有節(jié)點的最短路徑、K則最短路徑、實時最短路徑和指定必經(jīng)點的最短路徑問題。第五章為總結(jié)，提出文章的缺點與不足之處，談?wù)勛约旱南敕ǎ⑻岢霭l(fā)展期望。本題目的意義在于，用 java 軟件技術(shù)實現(xiàn)最短路徑算法在交通咨詢中的重要應(yīng)用，對模擬結(jié)果進行分析討論，為將來能夠有效解決各大城市的交通問題提供可靠的依據(jù)。本文所研究的算法內(nèi)容融合了除(4)之外的所有優(yōu)化策略，首先采用堆數(shù)據(jù)結(jié)構(gòu)將 Dijkstra 算法時間復(fù)雜度降至 O(N log N)，然后采用橢圓限制算法搜索區(qū)域，控制搜索規(guī)模，限定搜索方向，最后在本文提出的二樹算法中運用了并行運算思想，極大地降低了最短路徑查詢時間。鄰接表數(shù)據(jù)結(jié)構(gòu)已被證明是網(wǎng)絡(luò)表達中最有效率的數(shù)據(jù)結(jié)構(gòu)，在最短路徑算法中得到了廣泛應(yīng)用。第二章是本文的理論研究基礎(chǔ)，介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，著重討論了 Dij kstra 算法、Floyd 算法的運行機理。51959 年狄克斯特拉（Dijkstra）提出一個按路徑“長度”遞增的次序產(chǎn)生最短路徑的算法，即：把圖中所有的頂點分成兩組，第一組 S 包括已經(jīng)確定最短路徑的頂點，初始時只含有源點；第二組 VS 中包括尚未包括最短路徑的頂點，初始時含有圖中初源點之外的所有其他頂點。引進一個輔助向量 D，它的每個分量 D[i]表示當(dāng)前找到的從源點 V 到每個終點 的最短路徑的長度。FloydWarshall 算法的時間復(fù)雜度為 O(N3)，空間復(fù)雜度為 O(N2)。如果是更新它。在硬件或操作系統(tǒng)平臺上安裝一個 Java 平臺之后，Java 應(yīng)用程序就可運行。(2) java 面向?qū)ο螅簀ava 算是純面向?qū)ο?，?jquery 是更純的面向?qū)ο蟆?2) 編譯成 .class 字節(jié)碼文件 byte code（一種二進制文件） 。通過軟件的修補、替換完成系統(tǒng)的升級和更新?lián)Q代。（二）系統(tǒng)功能結(jié)構(gòu)1. 系統(tǒng)構(gòu)架設(shè)計首先總體的步驟是：迪克斯特拉算法的具體流程圖如下：13弗洛伊德算法的具體流程圖如下：14程序源代碼如下：//Floyd 算法public class ShortPathALG {private Drawing[] circleList = null。// 線段的個數(shù)private DrawJPanel drawJPanel = null。 i circleNum。}// 初始化線條的顏色private void changeLineColor() {for (int i = 1。//如果輸入的距離不能轉(zhuǎn)換成整形 默認(rèn)距離是 1 }catch(Exception e) {m = 1。} else {s = s + i + 。}s = dis。gv[i] = (d)。 lineList[i].yLocation == gv[j + 1]。// p 存放每對頂點之間的最短路徑int length = 0。 j length。 j length。// p 存放每對頂點之間的最短路徑for (i = 1。 j++) { int y = findTheMinInL()。 } }int i, j, k。 j++) {D[i][j] = data[i][j]。 j++) {if (i == j)// 對角線上的元素（即頂點自身之間）不予考慮continue。} else {dis += j + 沒有路徑\n。} else {dis += ppath(i, j) + j + \n 路徑長度為: + D[i][j] + \n。ppath(i, k)。 i 。import 。BufferedReader bufr = new BufferedReader(new InputStreamReader())。(=======請輸入頂點 + ( + 1) + 至其他各頂點的邊距=======)。flag = false。(請輸入頂點個數(shù)： )。 i sum。while(flag2){try {start = (())1。Point p1 = getTopointMin(arr, (i))。 i++) {// 當(dāng)已訪問 或 者是自身或者無該路徑時跳過。交通咨詢現(xiàn)代化作為城市現(xiàn)代化的重要內(nèi)容，首先應(yīng)是城市居民的生活交通現(xiàn)代化，這是以人為本原則的基本含義和根本要求。在這幾個月的畢業(yè)設(shè)計中，老師和同學(xué)們給予了我很大的幫助，因此我非常感謝他們，感謝他們這么長時間的陪伴與幫助。參 考 文 獻[1] 嚴(yán)蔚敏?；诼窂揭蕾嚨淖疃搪窂剿惴ǖ母倪M與實現(xiàn)[J].計算機工程與應(yīng)用，2022，(25)[9] 賀喜玲，季煥淑。圖論[M].北京，北京理工大學(xué)出版社，1997. [5] 陸鋒。感謝我的同學(xué)和朋友對我在生活和學(xué)習(xí)上的無私幫助，感謝他們給我?guī)砻恳惶斓臍g笑。調(diào)查表明人們在出行時往往更傾向于轉(zhuǎn)車次數(shù)較少的路線，這樣便降低了人們的辦事效率。}}}if (temp == null)return temp。}public static Point getTopointMin(ArrayListPoint arr, Point p) {Point temp = null。}}。(p)。flag = false。}}}// 該點到頂尖 id 的 距離。else {(至 頂點 + (i + 1) + 的距離 ：)。}public void changeFlag() {// 修改訪問狀態(tài)。// 點的 idprivate boolean flag = false。return mGraphCopy。ppath(k, j)。// 存放路徑String lineString = 。} elsedis += j + 路徑為: 。boolean c2Name = !circleList[j].()。 k++) {for (i = 1。// p 存放每對頂點之間的最短路徑for (i = 1。 jj 。 y++) { if (table[1][y] 0)// 如果 y 相鄰于 1 (y, length(1, y))。}}}19}}public void path_DIJKSTRA(int data[][]) {int i, j, k。 k length。// D 存放每對頂點之間的最短路徑值path = new int[length][length]。if (x || y) {lineList[i].setColor()。 j++) {for (i = 1。// 存放線段頂點int i = 1。 i++) {17for (int j = 1。}}// 輸出鄰接矩陣public void showMGraph() {String s = 最短路徑的鄰接矩陣是(無向圖)：\n。}// 初始化鄰接矩陣public void mGraphInitialize() {for (int i = 1。else {mGraph[i][j] = 32767。// 獲得線段對象數(shù)組circleNum = ()。private String dis = 。該交通咨詢系統(tǒng)設(shè)計共三部