【文章內(nèi)容簡介】 徑問題，單對節(jié)點(diǎn)間最短路徑、所有節(jié)點(diǎn)間最短路徑、k 則最短路徑、實(shí)時(shí)最短路徑、指定必經(jīng)節(jié)點(diǎn)的最短路徑以及前 N 條最短路徑問題等，本文的研究范疇屬于單對節(jié)點(diǎn)間最短路徑問題。(2) 按照網(wǎng)絡(luò)類型和表示方法分類，網(wǎng)絡(luò)可以分為稀疏網(wǎng)絡(luò)和非稀疏網(wǎng)絡(luò)，常用的表示方法有鄰接矩陣和鄰接表。鄰接矩陣方法能夠在 o(i)時(shí)間內(nèi)查詢到任意兩個(gè)節(jié)點(diǎn)之間是否有一條邊，它的空間復(fù)雜度為。現(xiàn)實(shí)生活中網(wǎng)絡(luò)節(jié)點(diǎn)往往很多，動(dòng)輒上萬，而且是稀疏網(wǎng)絡(luò)居多，比如城市路網(wǎng)，所以用鄰接矩陣表示既不現(xiàn)實(shí)，又浪費(fèi)空間。鄰接表是另一種存儲網(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)。鄰接表數(shù)據(jù)結(jié)構(gòu)已被證明是網(wǎng)絡(luò)表達(dá)中最有效率的數(shù)據(jù)結(jié)構(gòu)，在最短路徑算法中得到了廣泛應(yīng)用。Dijkstra 算法最簡單的實(shí)現(xiàn)方法是用一個(gè)鏈表或者數(shù)組來存儲所有頂點(diǎn)的集合，此時(shí)算法的時(shí)間復(fù)雜度是 .對于邊數(shù) M 遠(yuǎn)少于 的稀疏圖來說，為節(jié)省存儲空間，可以用鄰接表更有效的實(shí)現(xiàn)該算法。為縮短算法查詢時(shí)間，可以將一個(gè)二叉堆或者斐波納契堆用作優(yōu)先隊(duì)列來尋找最小的頂點(diǎn)。當(dāng)用到二叉堆的時(shí)候，算法所需的時(shí)間為 O((M + N) log N)。當(dāng)用斐波納契堆時(shí)，算法4時(shí)間復(fù)雜度為 O(M+N1ogN)。對于城市路網(wǎng)，由于 N/M 介于 和 2 之間所以采用堆數(shù)據(jù)結(jié)構(gòu)，Dijkstra 算法時(shí)間復(fù)雜度為 O(N log N)。（三）研究內(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)。（四）論文結(jié)構(gòu) 論文共分為六個(gè)章節(jié)，各章內(nèi)容組織如下: 第一章為緒論，首先敘述了本課題研究的背景意義，然后依次回顧了智能交通系統(tǒng)的發(fā)展歷程，介紹了最短路徑算法的研究現(xiàn)狀，最終引出論文的工作內(nèi)容并給出了論文組織結(jié)構(gòu)。第二章是本文的理論研究基礎(chǔ)，介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，著重討論了 Dij kstra 算法、Floyd 算法的運(yùn)行機(jī)理。第三章是介紹了系統(tǒng)的開發(fā)工具及系統(tǒng)的運(yùn)行環(huán)境。 第四章分析交通咨詢系統(tǒng)的最短路徑算法實(shí)現(xiàn)代碼的編寫。第五章簡要介紹了系統(tǒng)的界面設(shè)計(jì)。 第六章總結(jié)，提出文章的缺點(diǎn)與不足之處，談?wù)勛约旱南敕?，并提出發(fā)展期望。二、最短路徑算法相關(guān)原理本章介紹城市路網(wǎng)中各種限制搜索區(qū)域最短路徑算法，重點(diǎn)討論 Dijkstra 算法、Floyd 算法的實(shí)現(xiàn)原理。（一）Dijkstra 算法 Dijkstra 算法是一個(gè)按權(quán)值大小遞增的次序產(chǎn)生最優(yōu)路徑的算法，用于計(jì)算從有向圖中任意結(jié)點(diǎn)到其他結(jié)點(diǎn)的最優(yōu)路徑。設(shè)一個(gè)有向圖 G=(V,E),已知各邊的權(quán)值，以某指定點(diǎn) 為源點(diǎn)，求 到圖的其余各點(diǎn)的最短路徑。51959 年狄克斯特拉（Dijkstra）提出一個(gè)按路徑“長度”遞增的次序產(chǎn)生最短路徑的算法，即：把圖中所有的頂點(diǎn)分成兩組，第一組 S 包括已經(jīng)確定最短路徑的頂點(diǎn)，初始時(shí)只含有源點(diǎn)；第二組 VS 中包括尚未包括最短路徑的頂點(diǎn)，初始時(shí)含有圖中初源點(diǎn)之外的所有其他頂點(diǎn)。按路徑長度遞增的順序計(jì)算源點(diǎn)到各頂點(diǎn)的最短路徑，逐個(gè)把第二組中的頂點(diǎn)加到第一組中去，直至V=S。有向網(wǎng)用鄰接矩陣 cost[][]表示，其中規(guī)定：（1）如果兩個(gè)頂點(diǎn)之間無直接路徑，即弧對應(yīng)權(quán)值為無窮大；（ 2）兩個(gè)頂點(diǎn)之間有直接路徑 的，矩陣中的權(quán)值就是 弧對應(yīng)的公路長度；（3） 對應(yīng)的值為 0。S 集合初始存放最短路徑的源點(diǎn)，計(jì)算過程中將已經(jīng)確定了最短路徑的頂點(diǎn)加到 S 中去。Dist 數(shù)組最終存放源點(diǎn)到各頂點(diǎn)的最短路徑結(jié)果。Path 數(shù)組最終存放源點(diǎn)到個(gè)頂點(diǎn)的最短路徑經(jīng)過的頂點(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)值最小的弧。下一條長度次短的最短路徑是：假設(shè)該次短路徑的終點(diǎn)是 ，則這條路徑或者是 ，或者是 ，它的長度或者是從 V 到 弧上的權(quán)值，或者是 V 到 路徑長度與 到 的弧上權(quán)值之和。引進(jìn)一個(gè)輔助向量 D，它的每個(gè)分量 D[i]表示當(dāng)前找到的從源點(diǎn) V 到每個(gè)終點(diǎn) 的最短路徑的長度。設(shè)用帶權(quán)的鄰接矩陣 dist[i][j]來表示有向圖，dist[i][j]表示弧 上的權(quán)值，若 不存在，則置 dist[i][j]為某一最大值。向量 S 為已找到從 V 出發(fā)的最短路徑的終點(diǎn)的6集合，其初始值為空集。算法按下面的步驟進(jìn)行：① 從 V 出發(fā)到圖上其余各個(gè)頂點(diǎn)（終點(diǎn)） 可能達(dá)到的最短路徑長度的初始值為：D[i]=dist[ORDINAL(V)][i]，Vi∈V其中 ORDINAL(V)表示頂點(diǎn) V 在有向圖中的序號② 選擇 Vj，使D[j]=Min{D[i]|Vi S，Vi∈V}Vj 就是當(dāng)前求得的一條從 V 出發(fā)的最短路徑的終點(diǎn)，且令S=S∪{j}即將 j 加入到 S 集合中。③ 修改從 V 出發(fā)到集合 VS 上所有頂點(diǎn) Vk 可達(dá)到的最短路徑長度。如果D[j]+dist[j][k]D[k]則修改 D[k]為D[k]=D[j]+dist[j][k]④ 重復(fù)操作（2），（3）共 n1 次。最后求得從 V 到圖上其余各定點(diǎ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ì)算有向圖的傳遞閉包。FloydWarshall 算法的時(shí)間復(fù)雜度為 O(N3)，空間復(fù)雜度為 O(N2)。0 1 0 0 0 123 5 12 25 ∞ 0FBA FB FBC FD 無 無0 1 1 0 0 121 5 12 25 ∞ 0FBCA FB FBC FD 無 無1 1 1 0 0 121 5 12 25 ∞ 0FBCA FB FBC FD 無 無1 1 1 1 0 121 5 12 25 ∞ 0FBCA FB FBC FD 無 無8：Floyd 算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標(biāo)是尋找從點(diǎn) i 到點(diǎn) j 的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問題，我們需要為這個(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)過若干個(gè)節(jié)點(diǎn) k 到 j。所以，我們假設(shè) Dis(i,j)為節(jié)點(diǎn) u 到節(jié)點(diǎn) v 的最短路徑的距離，對于每一個(gè)節(jié)點(diǎn) k，我們檢查 Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，證明從 i 到 k 再到 j 的路徑比 i 直接到 j 的路徑短，我們便設(shè)置 Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn) k，Dis(i,j)中記錄的便是 i 到 j 的最短路徑的距離。：。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。 　　 u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 算法過程矩陣的計(jì)算 十字交叉法方法：兩條線，從左上角開始計(jì)算一直到右下角 如下所示給出矩陣，其中矩陣 A 是鄰接矩陣，而矩陣 Path 記錄 u,v 兩點(diǎn)之間最短路徑所必須經(jīng)過的點(diǎn)相應(yīng)計(jì)算方法如下：910最后 A3即為所求結(jié)果。三、開發(fā)工具與環(huán)境（一）Java 技術(shù)1. Java 簡介Java 是由 SunMicrosystems 公司于 1995 年 5 月推出的 Java 程序設(shè)計(jì)語言（以下簡稱 Java語言）和 Java 平臺的總稱。用 Java 實(shí)現(xiàn)的 HotJava 瀏覽器（支持 Javaapplet）顯示了 Java 的魅力：跨平臺、動(dòng)感的 Web、Inter 計(jì)算。從此，Java 被廣泛接受并推動(dòng)了 Web 的迅速發(fā)展，常用的瀏覽器現(xiàn)在均支持 Javaapplet。另一方面，Java 技術(shù)也不斷更新?！　ava 平臺由 Java 虛擬機(jī)（Java Virtual Machine）和 Java 應(yīng)用編程接口（Application ProgrammingInterface、簡稱 API）構(gòu)成。Java 應(yīng)用編程接口為 Java 應(yīng)用提供了一個(gè)獨(dú)立于操作系統(tǒng)的標(biāo)準(zhǔn)接口，可分為基本部分和擴(kuò)展部分。在硬件或操作系統(tǒng)平臺上安裝一個(gè) Java 平臺之后，Java 應(yīng)用程序就可運(yùn)行?，F(xiàn)在 Java 平臺已經(jīng)嵌入了幾乎所有的操作系統(tǒng)。這樣 Java 程序可以只編譯一次，就可以在各種系統(tǒng)中運(yùn)行。Java 應(yīng)用編程接口已經(jīng)從 版發(fā)展到 版。目前常用的 Java 平臺基于 ，最近版本為 。Java 分為三個(gè)體系 JavaSE，JavaEE，JavaME。Java 的特點(diǎn)是 ： (1) Java 的簡單性：和 C++相比，語法簡單了，取消了指針的語法；內(nèi)存分配和回收不需要我們來過渡關(guān)注，C++可以多繼承，但 java 只能是單繼承，相對于類來說。 （注：接口可以多繼承）使用 Asp 可以組合 HTML 頁、腳本命令和 ActiveX 組件以創(chuàng)建交互的 Web 頁和基于 Web 的功能強(qiáng)大的應(yīng)用程序。(2) java 面向?qū)ο螅簀ava 算是純面向?qū)ο?，?jquery 是更純的面向?qū)ο蟆?在 java 編程思想這本書說過， “Everything is object!” 這樣便于人類的構(gòu)思和設(shè)計(jì)，更符合人們的思考問題方式。(3) 分布式：主要還是用在 EJB 上。(4) 安全性：java 的語法限定了源程序的安全性，首先編譯器會進(jìn)行源代碼的第一步檢查。(5) 跨平臺：java 能夠跨越不同的操作系統(tǒng)平臺，平臺無關(guān)性 怎么跨平臺呢？ 主要是在不同的操作系統(tǒng)中，JVM 規(guī)范都是一樣的，被 JVM 加載成各個(gè)操作系統(tǒng)所支持的，屏蔽了底層操作系統(tǒng)的差異。(6) 高性能：開閉