【正文】 最短路徑算法分析及其在公交查詢的應(yīng)用[J]. 工程圖學(xué)學(xué)報(bào)，2022， （3）[7] 宋曉宇，于瀾洋，孫煥良，許景科。我將最誠摯的感謝獻(xiàn)給我的父母，我今天的成績也凝聚了他們辛勤的汗水。現(xiàn)實(shí)世界的交通網(wǎng)絡(luò)是復(fù)雜的，僅僅考慮道路網(wǎng)的時(shí)間損耗和長度分析很難29滿足實(shí)際需要，尤其是在城市交通網(wǎng)絡(luò)中，在不久的將來，本系統(tǒng)還將致力于通過分析城市道路狀況，交通管理設(shè)施，交通結(jié)構(gòu)及管理狀況，考慮道路的進(jìn)行和單行問題，排除阻礙交通的不通路，給出兩點(diǎn)之間的最優(yōu)路徑。return temp。for (int i = 0。// 單源最短路徑遍歷}public static void showDijkstra(ArrayListPoint arr, int i) {(頂點(diǎn) + (i + 1))。boolean flag2 =true。}}。}}class Dijkstra {public static void main(String[] args)throws IOException {ArrayListPoint point_arr = new ArrayListPoint()。int len = 0。}public boolean isVisit() {// 查看訪問狀態(tài)return flag。// 記錄總的點(diǎn)個(gè)數(shù)private TreeMapInteger, Integer thisPointMap = new TreeMapInteger, Integer()。import 。}// 得到鄰接矩陣對象的副本public int[][] getmGraphCopy() {mGraphCopy = new int[][]。k = path[i][j]。} elsedis += i + 。} else {dis = 從 + i + 到。 i++) {for (j = 1。 i++) {// 各節(jié)點(diǎn)之間的初始已知路徑及距離20for (j = 1。amp。 } for (int j = 1。D = new int[length][length]。 i length。 i length。}// 最短路徑算法 FLOYD 算法int D[][] = null。 i++) {boolean x = lineList[i].xLocation == gv[j]amp。gv = new int[() + 1]。 j++) {s = s + mGraph[i][j] + 。 i circleNum。 i++) {// 循環(huán)遍歷線條的起點(diǎn)與終點(diǎn)int m = 32767。// 初始化線條的顏色mGraphInitialize()。mGraph = new int[circleNum][circleNum]。// 要繪制的紅線路徑private int circleNum = 0。該交通咨詢系統(tǒng)要完成城市網(wǎng)絡(luò)圖的存儲，并要實(shí)現(xiàn)求任意一個(gè)城市頂點(diǎn)到其他城市頂點(diǎn)的最短路徑問題，還要實(shí)現(xiàn)任意兩個(gè)城市頂點(diǎn)間的最短路徑問題。所有這些，都要求系統(tǒng)提供足夠的手段進(jìn)行功能的調(diào)整和擴(kuò)充。(7) 多線程。Java 的特點(diǎn)是 ： (1) Java 的簡單性：和 C++相比，語法簡單了，取消了指針的語法；內(nèi)存分配和回收不需要我們來過渡關(guān)注，C++可以多繼承，但 java 只能是單繼承，相對于類來說。　　Java 平臺由 Java 虛擬機(jī)（Java Virtual Machine）和 Java 應(yīng)用編程接口（Application ProgrammingInterface、簡稱 API）構(gòu)成。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。最后求得從 V 到圖上其余各定點(diǎn)的最短路徑是依路徑長度遞增的序列。如下圖所示：由 F 到 A 的路徑有三條：F A：24；F B A：5+18=23；F B C A：5+7+9=21第一條最短路徑為與源點(diǎn) V 鄰接頂點(diǎn)的弧集合中，權(quán)值最小的弧。（一）Dijkstra 算法 Dijkstra 算法是一個(gè)按權(quán)值大小遞增的次序產(chǎn)生最優(yōu)路徑的算法，用于計(jì)算從有向圖中任意結(jié)點(diǎn)到其他結(jié)點(diǎn)的最優(yōu)路徑。（三）研究內(nèi)容 本文的研究范疇是智能交通系統(tǒng)中的最短路徑算法，研究領(lǐng)域是城市路網(wǎng)中的限制搜索區(qū)域最短路徑算法，研究內(nèi)容是典型城市路網(wǎng)中最短路徑算法的理論研究及實(shí)驗(yàn)驗(yàn)證，研究目的是保證查詢結(jié)果可靠的情況下，最大程度降低最短路徑查詢時(shí)間，研究方法是充分研究和利用城市路網(wǎng)的特征參數(shù)，降低最短路徑算法冗余度和復(fù)雜度，性能驗(yàn)證是軟件仿真預(yù)測和實(shí)測數(shù)據(jù)統(tǒng)計(jì)雙重評估標(biāo)準(zhǔn)?，F(xiàn)實(shí)生活中網(wǎng)絡(luò)節(jié)點(diǎn)往往很多，動輒上萬，而且是稀疏網(wǎng)絡(luò)居多，比如城市路網(wǎng)，所以用鄰接矩陣表示既不現(xiàn)實(shí)，又浪費(fèi)空間。創(chuàng)門在空間復(fù)雜度、時(shí)間復(fù)雜度、易實(shí)現(xiàn)性及應(yīng)用范圍等方面各具3特色但是因?yàn)?Dijkstra 算法可以給出最可靠的最短路徑，并且容易實(shí)現(xiàn)，所以備受青睞和并被廣泛應(yīng)用。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問題建立一個(gè)交通咨詢系統(tǒng)。第三章介紹最短路徑問題的幾種算法。從實(shí)際意義上講，沒有哪一種算法能夠適用于所有的網(wǎng)絡(luò)形式，并且在所有的網(wǎng)絡(luò)形式上具有很好的空間和時(shí)間復(fù)雜性。在交通咨詢方面，尋找交通網(wǎng)路中兩個(gè)城市之間最短的行車路線就是最短路徑問題的一個(gè)典型的例子。隨著現(xiàn)代生活節(jié)奏的加快，以及城市汽車數(shù)量的不斷增加，交通網(wǎng)絡(luò)也越來越發(fā)達(dá)，在交通工具和交通方式不斷更新的今天，人們在旅游、出差或者其他出行時(shí)，不僅會關(guān)心費(fèi)用問題，而且對里程和所需要的時(shí)間等問題也特別感興趣。本人完全意識到本聲明的法律后果由本人承擔(dān)。本科畢業(yè)論文(設(shè)計(jì))論文題目： 交通咨詢系統(tǒng)的最短路徑算法與實(shí)現(xiàn) I畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文） ，是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問題建立一個(gè)交通咨詢系統(tǒng)。在網(wǎng)絡(luò)通信領(lǐng)域，信息包傳遞的路徑選擇問題也與最短路徑息息相關(guān)。這些算法又具有各自的優(yōu)缺點(diǎn)。第四章交通咨詢系統(tǒng)的設(shè)計(jì)及實(shí)現(xiàn)。這樣的一個(gè)交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問題，比如任意一個(gè)城市到其他城市的最短路徑，或者任意兩個(gè)城市之間的最短路徑問題。經(jīng)典的 Dijkstra 算法的時(shí)間復(fù)雜度為 ，直接應(yīng)用到大規(guī)模城市路網(wǎng)時(shí)，最短路徑查詢時(shí)間難以令人接受，專家學(xué)者紛紛開展 Dij kstra 優(yōu)化算法研究，概括起來，以往研究者主要是從5 個(gè)方面對最短路徑算法進(jìn)行性能優(yōu)化：(1)基于數(shù)據(jù)存儲結(jié)構(gòu)的優(yōu)化，以空間換取時(shí)間； ( 2 )基于路網(wǎng)規(guī)模控制的優(yōu)化；(3)基于搜索策略的優(yōu)化；( 4 )優(yōu)先級隊(duì)列結(jié)構(gòu)的優(yōu)化； ( 5 )基于雙向搜索的并行計(jì)算優(yōu)化。鄰接表是另一種存儲網(wǎng)絡(luò)拓?fù)涞臄?shù)據(jù)結(jié)構(gòu)，它是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于交通網(wǎng)絡(luò)等稀疏圖，采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)空間復(fù)雜度僅為 O(M 十 N)，不存在存儲空間的浪費(fèi)。（四）論文結(jié)構(gòu) 論文共分為六個(gè)章節(jié)，各章內(nèi)容組織如下: 第一章為緒論，首先敘述了本課題研究的背景意義，然后依次回顧了智能交通系統(tǒng)的發(fā)展歷程，介紹了最短路徑算法的研究現(xiàn)狀，最終引出論文的工作內(nèi)容并給出了論文組織結(jié)構(gòu)。設(shè)一個(gè)有向圖 G=(V,E),已知各邊的權(quán)值，以某指定點(diǎn) 為源點(diǎn)，求 到圖的其余各點(diǎn)的最短路徑。下一條長度次短的最短路徑是：假設(shè)該次短路徑的終點(diǎn)是 ，則這條路徑或者是 ，或者是 ，它的長度或者是從 V 到 弧上的權(quán)值，或者是 V 到 路徑長度與 到 的弧上權(quán)值之和。例：對上圖，鄰接矩陣為最短路徑求解過程圖例，F(xiàn) 為源點(diǎn)；① 初始狀態(tài)，A B C D E FS D 求得 min{D}={24,5, ∞,25, ∞}=5，最短路徑 F B② 以 D[j]修改（即 F B 路徑長度修改）向量 D，A B C D E F0 0 0 0 0 124 5 ∞ 25 ∞ 0FA FB 無 FD 無 無7S D 求得 min{D}={23,12, 25, ∞}=12，最短路徑 F B C③ 以 D[j]修改（即 F B C 路徑長度修改）向量 D，A B C D E FS D 求得 min{D}={21, 25, ∞}=21，最短路徑 F B C A④ 以 D[j]修改（即 F B C A 路徑長度修改）向量 D，A B C D E FS D 求得 min{D}={25, ∞}=25，最短路徑 F D⑤ 以 D[j]修改（即 F D 路徑長度修改）向量 D，A B C D E FS D 求得 min{D}={∞}=∞，即 F E 無路徑（二）Floyd 算法FloydWarshall 算法（FloydWarshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。 　　 u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。Java 應(yīng)用編程接口為 Java 應(yīng)用提供了一個(gè)獨(dú)立于操作系統(tǒng)的標(biāo)準(zhǔn)接口，可分為基本部分和擴(kuò)展部分。 （注：接口可以多繼承）使用 Asp 可以組合 HTML 頁、腳本命令和 ActiveX 組件以創(chuàng)建交互的 Web 頁和基于 Web 的功能強(qiáng)大的應(yīng)用程序。11 的處理流程(1) 首先編輯 .java 源程序。而要實(shí)現(xiàn)這一點(diǎn)，應(yīng)通過系統(tǒng)的開放性來完成，既系統(tǒng)應(yīng)是一個(gè)開放系統(tǒng)，只要符合一定的規(guī)范，可以簡單的加入和減少系統(tǒng)的模塊，配置系統(tǒng)的硬件。故設(shè)計(jì)要分成三部分，一是建立網(wǎng)絡(luò)交通的存儲結(jié)構(gòu)，二是解決單源最短路徑問題；最后時(shí)限兩個(gè)城市之間的最短路徑問題。// 結(jié)點(diǎn)的個(gè)數(shù)private int lineNum = 0。// 為鄰接矩陣分配空間 0 行 、0 列 不用for (int i = 0。// 初始化鄰接矩陣path_FLOYD(getmGraphCopy())。try{m= (lineList[i].name)。 i++) {if (!circleList[i].()) {s = s + circleList[i].name + 。}s = s + \n。// 動態(tài)的決定數(shù)組的長度while (()) {String d = ()。amp。// D 存放每對頂點(diǎn)之間的最短路徑值int path[][] = null。 i++) {// 各節(jié)點(diǎn)之間的初始已知路徑及距離for (j = 1。 i++) {for (j = 1。// D 存放每對頂點(diǎn)之間的最短路徑值path = new int[length][length]。 j = () 1。 (((y) + length(y, jj)) (jj))) (jj, (y) + length(y, jj))。 j length。 j length。21}if (c2Name)