【正文】 ue。if (D[i][k] + D[k][j] D[i][j]) {// 從 i 經(jīng) k 到 j 的一條路徑更短D[i][j] = D[i][k] + D[k][j]。path[i][j]=k。}}}}}// 最短路徑輸出public String disPath(int i, int j) {// TODO Autogenerated method stubboolean c1Name = !circleList[i].()。boolean c2Name = !circleList[j].()。if (D[i][j] == 32767) {if (i != j) {if (c1Name) {dis = 從 + circleList[i].name + 到。} else {dis = 從 + i + 到。21}if (c2Name) {dis += circleList[j].name + 沒有路徑\n。} else {dis += j + 沒有路徑\n。}}} else {if (c1Name) {dis = 從 + circleList[i].name + 到。} elsedis = 從 + i + 到。if (c2Name) {dis += circleList[j].name + 路徑為: 。} elsedis += j + 路徑為: 。if (c1Name) {dis += circleList[i].name + 。} elsedis += i + 。if (c2Name) {dis += ppath(i, j) + circleList[j].name + \n 路徑長度為: + D[i][j]+ \n。} else {dis += ppath(i, j) + j + \n 路徑長度為: + D[i][j] + \n。}drawLineRed = i + + lineString + j。}return dis。}String s = 。// 存放路徑String lineString = 。// 劃紅線的路徑22private String ppath(int i, int j) {int k。k = path[i][j]。if (k == 1)return s。ppath(i, k)。if (!circleList[k].()) {s = s + circleList[k].name + 。} else {s = s + k + 。}lineString += k + 。ppath(k, j)。return s。}// 得到鄰接矩陣對(duì)象的副本public int[][] getmGraphCopy() {mGraphCopy = new int[][]。for (int i = 0。 i 。 i++)for (int j = 0。 j 。 j++)mGraphCopy[i][j] = mGraph[i][j]。return mGraphCopy。}}//Dijkstra 算法package Test。import 。import 。import 。import 。import 。23class Point {private int id。// 點(diǎn)的 idprivate boolean flag = false。// 標(biāo)志是否被遍歷int sum。// 記錄總的點(diǎn)個(gè)數(shù)private TreeMapInteger, Integer thisPointMap = new TreeMapInteger, Integer()。// 該點(diǎn)到各點(diǎn)的距離。BufferedReader bufr = new BufferedReader(new InputStreamReader())。Point(int sum) { // 構(gòu)造函數(shù) 帶有頂點(diǎn)個(gè)數(shù) = sum。}public void setId(int id) {// 設(shè)置頂點(diǎn) id = id。}public int getId() {// 獲得頂點(diǎn) idreturn 。}public void changeFlag() {// 修改訪問狀態(tài)。 = true。}public boolean isVisit() {// 查看訪問狀態(tài)return flag。}public void setLenToOther()throws IOException{// 初始化改點(diǎn)到各頂點(diǎn)的距離。(=======請(qǐng)輸入頂點(diǎn) + ( + 1) + 至其他各頂點(diǎn)的邊距=======)。for (int i = 0。 i sum。 i++) {if (i == )24(, 0)。else {(至 頂點(diǎn) + (i + 1) + 的距離 ：)。boolean flag =true。int len = 0。while(flag){try {len = (())。flag = false。} catch (NumberFormatException e) {(輸入有誤，請(qǐng)重新輸入：)。}}。(i, len)。}}}// 該點(diǎn)到頂尖 id 的 距離。public int lenToPointId(int id) {return (id)。}}class Dijkstra {public static void main(String[] args)throws IOException {ArrayListPoint point_arr = new ArrayListPoint()。// 存儲(chǔ)點(diǎn)集合BufferedReader bufr = new BufferedReader(new InputStreamReader())。(請(qǐng)輸入頂點(diǎn)個(gè)數(shù)： )。int sum = 0。boolean flag =true。while(flag){try {25sum = (())。flag = false。} catch (NumberFormatException e) {(輸入有誤，請(qǐng)重新輸入：)。}}。for (int i = 0。 i sum。 i++) {// 初始化Point p = new Point(sum)。(i)。()。(p)。}(請(qǐng)輸入起始頂點(diǎn) id ：)。boolean flag2 =true。int start = 0。while(flag2){try {start = (())1。if(start sum1 || start 0)throw new NumberFormatException()。flag2 = false。}catch (NumberFormatException e) {(輸入有誤，請(qǐng)重新輸入：)。}}。showDijkstra(point_arr, start)。// 單源最短路徑遍歷}public static void showDijkstra(ArrayListPoint arr, int i) {(頂點(diǎn) + (i + 1))。(i).changeFlag()。Point p1 = getTopointMin(arr, (i))。if (p1 == null)return。26int id = ()。showDijkstra(arr, id)。}public static Point getTopointMin(ArrayListPoint arr, Point p) {Point temp = null。int minLen = 。for (int i = 0。 i ()。 i++) {// 當(dāng)已訪問 或 者是自身或者無該路徑時(shí)跳過。if ((i).isVisit() || (i).getId() == () || (i) 0)continue。else {if ((i) minLen) {minLen = (i)。temp = (i)。}}}if (temp == null)return temp。else( @ + minLen + )。return temp。}}3. 測試數(shù)據(jù)及分析Floyd 算法輸出結(jié)果分析如下：27Dijkstra 算法運(yùn)行結(jié)果如下：28五、設(shè)計(jì)總結(jié)城市現(xiàn)代化的目的，說到底是為了人的現(xiàn)代化。交通咨詢現(xiàn)代化作為城市現(xiàn)代化的重要內(nèi)容，首先應(yīng)是城市居民的生活交通現(xiàn)代化，這是以人為本原則的基本含義和根本要求。一般來說，實(shí)現(xiàn)居民生活交通現(xiàn)代化（主要是交通咨詢的現(xiàn)代化）便可以滿足城市生產(chǎn)和經(jīng)營交通現(xiàn)代化的要求。交通咨詢系統(tǒng)服務(wù)于城市現(xiàn)代化發(fā)展戰(zhàn)略，以建設(shè)現(xiàn)代化交通為目標(biāo)，堅(jiān)持以人為本原則，優(yōu)化交通結(jié)構(gòu)，大力發(fā)展公共交通。本次設(shè)計(jì)只是實(shí)現(xiàn)了兩點(diǎn)之間最短路徑可行距離的查詢，而在現(xiàn)實(shí)生活中我們不僅要考慮兩點(diǎn)之間的最短距離，還要考慮轉(zhuǎn)車次數(shù)，這正是本次設(shè)計(jì)的不足之處。調(diào)查表明人們?cè)诔鲂袝r(shí)往往更傾向于轉(zhuǎn)車次數(shù)較少的路線，這樣便降低了人們的辦事效率。因此，完善的交通咨詢系統(tǒng)對(duì)兩點(diǎn)之間的最短路徑的查詢應(yīng)以轉(zhuǎn)車次數(shù)少為條件?，F(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)路徑。致謝時(shí)間過得很快，一轉(zhuǎn)眼四年的大學(xué)時(shí)間已近結(jié)尾，在這四年的生活學(xué)習(xí)中，許多老師和同學(xué)給予了我很多幫助。在這幾個(gè)月的畢業(yè)設(shè)計(jì)中，老師和同學(xué)們給予了我很大的幫助，因此我非常感謝他們，感謝他們這么長時(shí)間的陪伴與幫助。在這里我最想感謝的人就是指導(dǎo)老師。在畢業(yè)設(shè)計(jì)期間，指導(dǎo)老師的悉心教導(dǎo)深刻地印在我心里，她平易近人，知識(shí)淵博，又對(duì)我們嚴(yán)格要求和嚴(yán)厲督促，這時(shí)的我在即將離開大學(xué)之際又多了一份很美好的回憶，也增加了自身的知識(shí)寬度。當(dāng)然還要感學(xué)院各位老師對(duì)我的培養(yǎng)和關(guān)心，是他們?yōu)槲覄?chuàng)造了良好的學(xué)習(xí)環(huán)境。感謝我的同學(xué)和朋友對(duì)我在生活和學(xué)習(xí)上的無私幫助，感謝他們給我?guī)砻恳惶斓臍g笑。感謝每位同學(xué)在論文寫作期間的大力支持與鼓勵(lì)。我將最誠摯的感謝獻(xiàn)給我的父母，我今天的成績也凝聚了他們辛勤的汗水。正是因?yàn)楦改笇?duì)我的關(guān)心、教誨和鼓勵(lì)使我能夠好好地完成學(xué)業(yè)，并向更高的目標(biāo)奮斗。參 考 文 獻(xiàn)[1] 嚴(yán)蔚敏。數(shù)據(jù)結(jié)構(gòu)（C 語言版）[M].北京，清華大學(xué)出版社，1997.[2] 王海英，黃強(qiáng)，李傳濤。圖論算法及其 MATLAB 實(shí)現(xiàn)[M].北京，北京航空航天大學(xué)出版社，2022.[3] 周先曙。最短路徑問題及其解法研究[J],電腦知識(shí)與技術(shù)，2022， （06）.[4] 王朝瑞。圖論[M].北京，北京理工大學(xué)出版社，1997. [5] 陸鋒。最短路徑算法：分類體系與研究進(jìn)展[J]. 測繪學(xué)報(bào)，2022， （3）：269275[6] 陳簫楓，蔡秀云，唐德強(qiáng)。最短路徑算法分析及其在公交查詢的應(yīng)用[J]. 工程圖學(xué)學(xué)報(bào)，2022， （3）[7] 宋曉宇，于瀾洋，孫煥良，許景科。交通網(wǎng)絡(luò)中出現(xiàn)阻塞路徑情況下增量路徑查找算法[J].沈30陽建筑大學(xué)學(xué)報(bào)（自然科學(xué)版） ，2022， （4）[8] 張池軍，楊永健，趙洪波?；诼窂揭蕾嚨淖疃搪窂剿惴ǖ母倪M(jìn)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2022，(25)[9] 賀喜玲，季煥淑。最短路徑算法[J].大科技（科技天地） ，2022，(6)[10] 李擎，謝四江，童新海，王志良。一種用于車輛最短路徑規(guī)劃的自適應(yīng)遺傳算法及其與 Dijkstra 和 A^＊算法的比較[J]. 北京科技大學(xué)學(xué)報(bào),2022,(11):10821086