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