【正文】 va 源程序。(6) 高性能：開閉原則對(duì)擴(kuò)展開放，對(duì)修改關(guān)閉 java 是即時(shí)編譯的。(4) 安全性：java 的語(yǔ)法限定了源程序的安全性，首先編譯器會(huì)進(jìn)行源代碼的第一步檢查。 在 java 編程思想這本書說(shuō)過(guò)， “Everything is object!” 這樣便于人類的構(gòu)思和設(shè)計(jì)，更符合人們的思考問(wèn)題方式。 （注：接口可以多繼承）使用 Asp 可以組合 HTML 頁(yè)、腳本命令和 ActiveX 組件以創(chuàng)建交互的 Web 頁(yè)和基于 Web 的功能強(qiáng)大的應(yīng)用程序。Java 分為三個(gè)體系 JavaSE，JavaEE，JavaME。Java 應(yīng)用編程接口已經(jīng)從 版發(fā)展到 版。現(xiàn)在 Java 平臺(tái)已經(jīng)嵌入了幾乎所有的操作系統(tǒng)。Java 應(yīng)用編程接口為 Java 應(yīng)用提供了一個(gè)獨(dú)立于操作系統(tǒng)的標(biāo)準(zhǔn)接口，可分為基本部分和擴(kuò)展部分。另一方面，Java 技術(shù)也不斷更新。用 Java 實(shí)現(xiàn)的 HotJava 瀏覽器（支持 Javaapplet）顯示了 Java 的魅力：跨平臺(tái)、動(dòng)感的 Web、Inter 計(jì)算。 算法過(guò)程矩陣的計(jì)算 十字交叉法方法：兩條線，從左上角開始計(jì)算一直到右下角 如下所示給出矩陣，其中矩陣 A 是鄰接矩陣，而矩陣 Path 記錄 u,v 兩點(diǎn)之間最短路徑所必須經(jīng)過(guò)的點(diǎn)相應(yīng)計(jì)算方法如下：910最后 A3即為所求結(jié)果。 　　 u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。：。從動(dòng)態(tài)規(guī)劃的角度看問(wèn)題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋（這個(gè)詮釋正是動(dòng)態(tài)規(guī)劃最富創(chuàng)造力的精華所在）從任意節(jié)點(diǎn) i 到任意節(jié)點(diǎn) j 的最短路徑不外乎 2 種可能，1 是直接從 i 到 j，2 是從 i 經(jīng)過(guò)若干個(gè)節(jié)點(diǎn) k 到 j。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ī)劃算法。例：對(duì)上圖，鄰接矩陣為最短路徑求解過(guò)程圖例，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 路徑長(zhǎng)度修改）向量 D，A B C D E F0 0 0 0 0 124 5 ∞ 25 ∞ 0FA FB 無(wú) FD 無(wú) 無(wú)7S D 求得 min{D}={23,12, 25, ∞}=12，最短路徑 F B C③ 以 D[j]修改（即 F B C 路徑長(zhǎng)度修改）向量 D，A B C D E FS D 求得 min{D}={21, 25, ∞}=21，最短路徑 F B C A④ 以 D[j]修改（即 F B C A 路徑長(zhǎng)度修改）向量 D，A B C D E FS D 求得 min{D}={25, ∞}=25，最短路徑 F D⑤ 以 D[j]修改（即 F D 路徑長(zhǎng)度修改）向量 D，A B C D E FS D 求得 min{D}={∞}=∞，即 F E 無(wú)路徑（二）Floyd 算法FloydWarshall 算法（FloydWarshall algorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。如果D[j]+dist[j][k]D[k]則修改 D[k]為D[k]=D[j]+dist[j][k]④ 重復(fù)操作（2），（3）共 n1 次。算法按下面的步驟進(jìn)行：① 從 V 出發(fā)到圖上其余各個(gè)頂點(diǎn)（終點(diǎn)） 可能達(dá)到的最短路徑長(zhǎng)度的初始值為：D[i]=dist[ORDINAL(V)][i]，Vi∈V其中 ORDINAL(V)表示頂點(diǎn) V 在有向圖中的序號(hào)② 選擇 Vj，使D[j]=Min{D[i]|Vi S，Vi∈V}Vj 就是當(dāng)前求得的一條從 V 出發(fā)的最短路徑的終點(diǎn)，且令S=S∪{j}即將 j 加入到 S 集合中。設(shè)用帶權(quán)的鄰接矩陣 dist[i][j]來(lái)表示有向圖，dist[i][j]表示弧 上的權(quán)值，若 不存在，則置 dist[i][j]為某一最大值。下一條長(zhǎng)度次短的最短路徑是：假設(shè)該次短路徑的終點(diǎn)是 ，則這條路徑或者是 ，或者是 ，它的長(zhǎng)度或者是從 V 到 弧上的權(quán)值，或者是 V 到 路徑長(zhǎng)度與 到 的弧上權(quán)值之和。Path 數(shù)組最終存放源點(diǎn)到個(gè)頂點(diǎn)的最短路徑經(jīng)過(guò)的頂點(diǎn)。S 集合初始存放最短路徑的源點(diǎn)，計(jì)算過(guò)程中將已經(jīng)確定了最短路徑的頂點(diǎn)加到 S 中去。按路徑長(zhǎng)度遞增的順序計(jì)算源點(diǎn)到各頂點(diǎn)的最短路徑，逐個(gè)把第二組中的頂點(diǎn)加到第一組中去，直至V=S。設(shè)一個(gè)有向圖 G=(V,E),已知各邊的權(quán)值，以某指定點(diǎn) 為源點(diǎn)，求 到圖的其余各點(diǎn)的最短路徑。二、最短路徑算法相關(guān)原理本章介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，重點(diǎn)討論 Dijkstra 算法、Floyd 算法的實(shí)現(xiàn)原理。第五章簡(jiǎn)要介紹了系統(tǒng)的界面設(shè)計(jì)。第三章是介紹了系統(tǒng)的開發(fā)工具及系統(tǒng)的運(yùn)行環(huán)境。（四）論文結(jié)構(gòu) 論文共分為六個(gè)章節(jié)，各章內(nèi)容組織如下: 第一章為緒論，首先敘述了本課題研究的背景意義，然后依次回顧了智能交通系統(tǒng)的發(fā)展歷程，介紹了最短路徑算法的研究現(xiàn)狀，最終引出論文的工作內(nèi)容并給出了論文組織結(jié)構(gòu)。對(duì)于城市路網(wǎng)，由于 N/M 介于 和 2 之間所以采用堆數(shù)據(jù)結(jié)構(gòu)，Dijkstra 算法時(shí)間復(fù)雜度為 O(N log N)。當(dāng)用到二叉堆的時(shí)候，算法所需的時(shí)間為 O((M + N) log N)。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)該算法。鄰接表是另一種存儲(chǔ)網(wǎng)絡(luò)拓?fù)涞臄?shù)據(jù)結(jié)構(gòu)，它是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于交通網(wǎng)絡(luò)等稀疏圖，采用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)空間復(fù)雜度僅為 O(M 十 N)，不存在存儲(chǔ)空間的浪費(fèi)。鄰接矩陣方法能夠在 o(i)時(shí)間內(nèi)查詢到任意兩個(gè)節(jié)點(diǎn)之間是否有一條邊，它的空間復(fù)雜度為。最短路徑問(wèn)題具體可細(xì)分為以下幾種，單源最短路徑問(wèn)題，單對(duì)節(jié)點(diǎn)間最短路徑、所有節(jié)點(diǎn)間最短路徑、k 則最短路徑、實(shí)時(shí)最短路徑、指定必經(jīng)節(jié)點(diǎn)的最短路徑以及前 N 條最短路徑問(wèn)題等，本文的研究范疇屬于單對(duì)節(jié)點(diǎn)間最短路徑問(wèn)題。由于問(wèn)題類型、網(wǎng)絡(luò)特性的不同，最短路徑算法也表現(xiàn)出多樣性。經(jīng)典的 Dijkstra 算法的時(shí)間復(fù)雜度為 ，直接應(yīng)用到大規(guī)模城市路網(wǎng)時(shí)，最短路徑查詢時(shí)間難以令人接受，專家學(xué)者紛紛開展 Dij kstra 優(yōu)化算法研究，概括起來(lái)，以往研究者主要是從5 個(gè)方面對(duì)最短路徑算法進(jìn)行性能優(yōu)化：(1)基于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的優(yōu)化，以空間換取時(shí)間； ( 2 )基于路網(wǎng)規(guī)?？刂频膬?yōu)化；(3)基于搜索策略的優(yōu)化；( 4 )優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)的優(yōu)化； ( 5 )基于雙向搜索的并行計(jì)算優(yōu)化。常用的路徑規(guī)劃方法有: 平行最短路徑搜索算法，蟻群算法，基于矩陣負(fù)載平衡的啟發(fā)算法, EBSP*算法和 Dijkstra 算法等。國(guó)內(nèi)外大量專家學(xué)者對(duì)此問(wèn)題進(jìn)行了深入研究。（二）研究現(xiàn)狀本節(jié)闡述三方面問(wèn)題，首先簡(jiǎn)要回顧最短路徑算法研究現(xiàn)狀，然后概要總結(jié)最短路徑算法分類，最后簡(jiǎn)單論述最短路徑算法的時(shí)間復(fù)雜度。這樣的一個(gè)交通系統(tǒng)可以回答人們提出的有關(guān)交通的所有問(wèn)題，比如任意一個(gè)城市到其他城市的最短路徑，或者任意兩個(gè)城市之間的最短路徑問(wèn)題。隨著交通網(wǎng)絡(luò)越來(lái)越發(fā)達(dá)，人們?cè)诼糜?、出差或者其他出行時(shí)，不僅會(huì)關(guān)心費(fèi)用問(wèn)題，而且對(duì)里程和所需要的時(shí)間等問(wèn)題也特別感興趣。而且在必要的時(shí)候能夠把道路、車輛、城市的發(fā)展需求等，大都與交通有關(guān)的基本因素歸為一體，在這些基本因素的基礎(chǔ)上，采用信息通信技術(shù)、信息自動(dòng)采集技術(shù)、電子技術(shù)、網(wǎng)絡(luò)技術(shù)、自動(dòng)控制以及其他的科學(xué)技術(shù)把它們聯(lián)系起來(lái)，開發(fā)一個(gè)可供模擬操作的城市交通管理系統(tǒng)。2一、緒 論（一）課題的背景和意義現(xiàn)如今，我國(guó)的各大城市都有著交通擁堵、道路堵塞和交通事故的頻繁發(fā)生，這些都隨著城市私家車的不斷增加和城市汽車交通運(yùn)輸?shù)募涌彀l(fā)展越來(lái)越困擾著我們的生活，并且汽車工業(yè)發(fā)展所引發(fā)的道路交通不能滿足實(shí)際需求的種種交通問(wèn)題也越來(lái)越嚴(yán)重，越來(lái)越突出。第四章交通咨詢系統(tǒng)的設(shè)計(jì)及實(shí)現(xiàn)。第二章介紹所要用到的技術(shù)原理。本文就從上述幾類來(lái)分別介紹最短路徑的幾種常用算法，并介紹最短路徑問(wèn)題中的算法改進(jìn)。在交通網(wǎng)絡(luò)的路徑分析中，單源最短路徑問(wèn)題更具有普遍意義，其算法有很多種，其中采用貪心及啟發(fā)策略的Dijkstra算法是目前最完善的，這是荷蘭計(jì)算機(jī)科學(xué)教授Edger (19302022)在1959年發(fā)現(xiàn)的一個(gè)算法，它以極強(qiáng)的抗差性得到普及和應(yīng)用。這些算法又具有各自的優(yōu)缺點(diǎn)。近年來(lái)，對(duì)最短路徑研究的熱度依然不減，并且時(shí)間復(fù)雜度也降得越來(lái)越低。這樣圖中所表示的最短路徑，就是對(duì)句子最好的解釋。在圖像分割問(wèn)題中，最短路徑也有直接的應(yīng)用：在語(yǔ)音識(shí)別中一個(gè)主要的問(wèn)題就是識(shí)別同音詞，例如，to、two、too。在網(wǎng)絡(luò)通信領(lǐng)域，信息包傳遞的路徑選擇問(wèn)題也與最短路徑息息相關(guān)。最短路徑問(wèn)題最直接的應(yīng)用當(dāng)數(shù)在地理信息領(lǐng)域中，例如：GIS網(wǎng)絡(luò)分析、城市規(guī)劃、電子導(dǎo)航等等。針對(duì)現(xiàn)代交通網(wǎng)絡(luò)現(xiàn)狀特點(diǎn)，分析和研究適合道路的經(jīng)典最短路徑算法，探討了在交通網(wǎng)絡(luò)路線優(yōu)化過(guò)程中需要特別處理的幾個(gè)問(wèn)題，并在理論上給出相應(yīng)的合理的解決方案。本文通過(guò)對(duì)幾個(gè)常見(jiàn)的最短路徑算法的分析，研究和實(shí)現(xiàn)，即經(jīng)典的 Dijkstra 算法、Floyd算法。為了能夠更方便人們的出行，我們就應(yīng)該以最短路徑問(wèn)題建立一個(gè)交通咨詢系統(tǒng)。圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準(zhǔn)用徒手畫3）畢業(yè)論文須用 A4 單面打印，論文 50 頁(yè)以上的雙面打印4）圖表應(yīng)繪制于無(wú)格子的頁(yè)面上5）軟件工程類課題應(yīng)有程序清單，并提供電子文檔1）設(shè)計(jì)（論文）2）附件：按照任務(wù)書、開題報(bào)告、外文譯文、譯文原文（復(fù)印件）次序裝訂IV目錄序 言 ...........................................................................................................1一、緒 論 ....................................................................................................2（一）課題的背景和意義 ..................................................................................................2（二）研究現(xiàn)狀 ..................................................................................................................2 ....................................................................................................................2