【正文】 ................................................................................26五、設(shè)計(jì)總結(jié) .............................................................................................28V致謝 ............................................................................................................29參 考 文 獻(xiàn) ...............................................................................................29交通咨詢系統(tǒng)的最短路徑算法與實(shí)現(xiàn)內(nèi) 容 摘 要目前在交通咨詢領(lǐng)域，最短路徑算法的研究和應(yīng)用越來(lái)越多，其中最短路徑算法的效率問(wèn)題是普遍關(guān)注并且在實(shí)際應(yīng)用中迫切需要解決的問(wèn)題。本文通過(guò)對(duì)幾個(gè)常見(jiàn)的最短路徑算法的分析，研究和實(shí)現(xiàn)，即經(jīng)典的 Dijkstra 算法、Floyd算法。最短路徑問(wèn)題最直接的應(yīng)用當(dāng)數(shù)在地理信息領(lǐng)域中，例如：GIS網(wǎng)絡(luò)分析、城市規(guī)劃、電子導(dǎo)航等等。在圖像分割問(wèn)題中，最短路徑也有直接的應(yīng)用：在語(yǔ)音識(shí)別中一個(gè)主要的問(wèn)題就是識(shí)別同音詞，例如，to、two、too。近年來(lái)，對(duì)最短路徑研究的熱度依然不減，并且時(shí)間復(fù)雜度也降得越來(lái)越低。在交通網(wǎng)絡(luò)的路徑分析中，單源最短路徑問(wèn)題更具有普遍意義，其算法有很多種，其中采用貪心及啟發(fā)策略的Dijkstra算法是目前最完善的，這是荷蘭計(jì)算機(jī)科學(xué)教授Edger (19302022)在1959年發(fā)現(xiàn)的一個(gè)算法，它以極強(qiáng)的抗差性得到普及和應(yīng)用。第二章介紹所要用到的技術(shù)原理。2一、緒 論（一）課題的背景和意義現(xiàn)如今，我國(guó)的各大城市都有著交通擁堵、道路堵塞和交通事故的頻繁發(fā)生，這些都隨著城市私家車的不斷增加和城市汽車交通運(yùn)輸?shù)募涌彀l(fā)展越來(lái)越困擾著我們的生活，并且汽車工業(yè)發(fā)展所引發(fā)的道路交通不能滿足實(shí)際需求的種種交通問(wèn)題也越來(lái)越嚴(yán)重，越來(lái)越突出。隨著交通網(wǎng)絡(luò)越來(lái)越發(fā)達(dá)，人們?cè)诼糜?、出差或者其他出行時(shí)，不僅會(huì)關(guān)心費(fèi)用問(wèn)題，而且對(duì)里程和所需要的時(shí)間等問(wèn)題也特別感興趣。（二）研究現(xiàn)狀本節(jié)闡述三方面問(wèn)題，首先簡(jiǎn)要回顧最短路徑算法研究現(xiàn)狀，然后概要總結(jié)最短路徑算法分類，最后簡(jiǎn)單論述最短路徑算法的時(shí)間復(fù)雜度。常用的路徑規(guī)劃方法有: 平行最短路徑搜索算法，蟻群算法，基于矩陣負(fù)載平衡的啟發(fā)算法, EBSP*算法和 Dijkstra 算法等。由于問(wèn)題類型、網(wǎng)絡(luò)特性的不同，最短路徑算法也表現(xiàn)出多樣性。鄰接矩陣方法能夠在 o(i)時(shí)間內(nèi)查詢到任意兩個(gè)節(jié)點(diǎn)之間是否有一條邊，它的空間復(fù)雜度為。Dijkstra 算法最簡(jiǎn)單的實(shí)現(xiàn)方法是用一個(gè)鏈表或者數(shù)組來(lái)存儲(chǔ)所有頂點(diǎn)的集合，此時(shí)算法的時(shí)間復(fù)雜度是 .對(duì)于邊數(shù) M 遠(yuǎn)少于 的稀疏圖來(lái)說(shuō)，為節(jié)省存儲(chǔ)空間，可以用鄰接表更有效的實(shí)現(xiàn)該算法。對(duì)于城市路網(wǎng)，由于 N/M 介于 和 2 之間所以采用堆數(shù)據(jù)結(jié)構(gòu)，Dijkstra 算法時(shí)間復(fù)雜度為 O(N log N)。第三章是介紹了系統(tǒng)的開(kāi)發(fā)工具及系統(tǒng)的運(yùn)行環(huán)境。二、最短路徑算法相關(guān)原理本章介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，重點(diǎn)討論 Dijkstra 算法、Floyd 算法的實(shí)現(xiàn)原理。按路徑長(zhǎng)度遞增的順序計(jì)算源點(diǎn)到各頂點(diǎn)的最短路徑，逐個(gè)把第二組中的頂點(diǎn)加到第一組中去，直至V=S。Path 數(shù)組最終存放源點(diǎn)到個(gè)頂點(diǎn)的最短路徑經(jīng)過(guò)的頂點(diǎn)。設(shè)用帶權(quán)的鄰接矩陣 dist[i][j]來(lái)表示有向圖，dist[i][j]表示弧 上的權(quán)值，若 不存在，則置 dist[i][j]為某一最大值。如果D[j]+dist[j][k]D[k]則修改 D[k]為D[k]=D[j]+dist[j][k]④ 重復(fù)操作（2），（3）共 n1 次。0 1 0 0 0 123 5 12 25 ∞ 0FBA FB FBC FD 無(wú) 無(wú)0 1 1 0 0 121 5 12 25 ∞ 0FBCA FB FBC FD 無(wú) 無(wú)1 1 1 0 0 121 5 12 25 ∞ 0FBCA FB FBC FD 無(wú) 無(wú)1 1 1 1 0 121 5 12 25 ∞ 0FBCA FB FBC FD 無(wú) 無(wú)8：Floyd 算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。：。 算法過(guò)程矩陣的計(jì)算 十字交叉法方法：兩條線，從左上角開(kāi)始計(jì)算一直到右下角 如下所示給出矩陣，其中矩陣 A 是鄰接矩陣，而矩陣 Path 記錄 u,v 兩點(diǎn)之間最短路徑所必須經(jīng)過(guò)的點(diǎn)相應(yīng)計(jì)算方法如下：910最后 A3即為所求結(jié)果。另一方面，Java 技術(shù)也不斷更新?，F(xiàn)在 Java 平臺(tái)已經(jīng)嵌入了幾乎所有的操作系統(tǒng)。Java 分為三個(gè)體系 JavaSE，JavaEE，JavaME。 在 java 編程思想這本書說(shuō)過(guò)， “Everything is object!” 這樣便于人類的構(gòu)思和設(shè)計(jì)，更符合人們的思考問(wèn)題方式。(6) 高性能：開(kāi)閉原則對(duì)擴(kuò)展開(kāi)放，對(duì)修改關(guān)閉 java 是即時(shí)編譯的。 (3) 最后被 java 虛擬機(jī)（JVM）加載解釋并執(zhí)行。例如數(shù)據(jù)表中用戶選擇字段方式的改變，用戶查詢的需求也會(huì)不斷的更新和完善。系統(tǒng)的易用性和易維護(hù)性：要實(shí)現(xiàn)這一點(diǎn)，就要求系統(tǒng)應(yīng)該盡量使用用戶熟悉的術(shù)語(yǔ)和中文信息的界面；針對(duì)用戶可能出現(xiàn)的使用問(wèn)題，要提供足夠的在線幫助，縮短用戶對(duì)系統(tǒng)熟悉的過(guò)程。12用鄰接矩陣來(lái)存儲(chǔ)交通網(wǎng)絡(luò)圖的信息，運(yùn)用迪杰斯特拉算法實(shí)現(xiàn)圖上單源最短路徑問(wèn)題，然后運(yùn)用費(fèi)洛伊德算法實(shí)現(xiàn)圖中任意一對(duì)頂點(diǎn)間最短路徑問(wèn)題，這樣就會(huì)實(shí)現(xiàn)旅客所要咨詢的問(wèn)題。// 用于存放結(jié)點(diǎn)private Drawing[] lineList = null。// 最短路徑結(jié)果15private String drawLineRed = 。public ShortPathALG(DrawJPanel draw) {drawJPanel = draw。// 獲得結(jié)點(diǎn)的個(gè)數(shù)lineNum = ()。 i++) {// 初始化鄰接矩陣 全賦值為 1 （距離不可能是負(fù)數(shù)）for (int j = 0。}}}changeLineColor()。 i lineNum。 i lineNum。}// 構(gòu)建無(wú)向圖if (lineList[i].())m = 1。for (int i = 1。}}s = s + \n。 j circleNum。lineColor()。StringTokenizer tokenizer = new StringTokenizer(drawLineRed, )。// 將字符串轉(zhuǎn)換為整型i++。 i lineNum。boolean y = lineList[i].yLocation == gv[j]amp。}}}18()。public void path_FLOYD(int data[][]) {int i, j, k。// p 存放每對(duì)頂點(diǎn)之間的最短路徑for (i = 1。 j++) {D[i][j] = data[i][j]。 k++) {for (i = 1。 j++) {if (i == j)// 對(duì)角線上的元素（即頂點(diǎn)自身之間）不予考慮continue。length = 。 i length。 else (y, )。 (y)。 jj++) { if(table[y][jj]0) if ((jj) amp。length = 。 i length。//path[i][j]= 1。 i length。if (D[i][k] + D[k][j] D[i][j]) {// 從 i 經(jīng) k 到 j 的一條路徑更短D[i][j] = D[i][k] + D[k][j]。if (D[i][j] == 32767) {if (i != j) {if (c1Name) {dis = 從 + circleList[i].name + 到。}}} else {if (c1Name) {dis = 從 + circleList[i].name + 到。if (c1Name) {dis += circleList[i].name + 。}drawLineRed = i + + lineString + j。// 劃紅線的路徑22private String ppath(int i, int j) {int k。if (!circleList[k].()) {s = s + circleList[k].name + 。return s。 i++)for (int j = 0。}}//Dijkstra 算法package Test。import 。// 標(biāo)志是否被遍歷int sum。Point(int sum) { // 構(gòu)造函數(shù) 帶有頂點(diǎn)個(gè)數(shù) = sum。 = true。for (int i = 0。boolean flag =true。} catch (NumberFormatException e) {(輸入有誤，請(qǐng)重新輸入：)。public int lenToPointId(int id) {return (id)。int sum = 0。} catch (NumberFormatException e) {(輸入有誤，請(qǐng)重新輸入：)。 i++) {// 初始化Point p = new Point(sum)。}(請(qǐng)輸入起始頂點(diǎn) id ：)。if(start sum1 || start 0)throw new NumberFormatException()。showDijkstra(point_arr, start)。if (p1 == null)return。int minLen = 。if ((i).isVisit() || (i).getId() == () || (i) 0)continue。else( + minLen + )。一般來(lái)說(shuō)，實(shí)現(xiàn)居民生活交通現(xiàn)代化（主要是交通咨詢的現(xiàn)代化）便可以滿足城市生產(chǎn)和經(jīng)營(yíng)交通現(xiàn)代化的要求。因此，完善的交通咨詢系統(tǒng)對(duì)兩點(diǎn)之間的最短路徑的查詢應(yīng)以轉(zhuǎn)車次數(shù)少為條件。在這里我最想感謝的人就是指導(dǎo)老師。感謝每位同學(xué)在論文寫作期間的大力支持與鼓勵(lì)。數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言版）[M].北京，清華大學(xué)出版社，1997.[2] 王海英，黃強(qiáng)，李傳濤。最短路徑算法：分類體系與研究進(jìn)展[J]. 測(cè)繪學(xué)報(bào)，2022， （3）：269275[6] 陳簫楓，蔡秀云，唐德強(qiáng)。最短路徑算法[J].大科技（科技天地） ，2022，(6)[10] 李擎，謝四江，童新海，王志良。交通網(wǎng)絡(luò)中出現(xiàn)阻塞路徑情況下增量路徑查找算法[J].沈30陽(yáng)建筑大學(xué)學(xué)報(bào)（自然科學(xué)版） ，2022， （4）[8] 張池軍，楊永健，趙洪波。最短路徑問(wèn)題及其解法研究[J],電腦知識(shí)與技術(shù)，2022， （06）.[4] 王朝瑞。正是因?yàn)楦改笇?duì)我的關(guān)心、教誨和鼓勵(lì)使我能夠好好地完成學(xué)業(yè)，并向更高的目標(biāo)奮斗。當(dāng)然還要感學(xué)院各位老師對(duì)我的培養(yǎng)和關(guān)心，是他們?yōu)槲覄?chuàng)造了良好的學(xué)習(xí)環(huán)境。致謝時(shí)間過(guò)得很快，一轉(zhuǎn)眼四年的大學(xué)時(shí)間已近結(jié)尾，在這四年的生活學(xué)習(xí)中，許多老師和同學(xué)給予了我很多幫助。本次設(shè)計(jì)只是實(shí)現(xiàn)了兩點(diǎn)之間最短路徑可行距離的查詢，而在現(xiàn)實(shí)生活中我們不僅要考慮兩點(diǎn)之間的最短距離，還要考慮轉(zhuǎn)車次數(shù)，這正是本次設(shè)計(jì)的不足之處。}}3. 測(cè)試數(shù)據(jù)及分析Floyd 算法輸出結(jié)