交通網(wǎng)絡(luò)限制條件下的最短路問題研究.pdf

1、一直以來，最短路算法是計(jì)算機(jī)科學(xué)、數(shù)學(xué)、地理信息系統(tǒng)和交通科學(xué)研究的熱點(diǎn)，與最短路算法相關(guān)的問題多種多樣，近年來隨著地理信息系統(tǒng)(GIS)與智能交通系統(tǒng)(ITS)的結(jié)合，最短路問題在交通地理信息系統(tǒng)中有著十分重要的位置，尤其是對(duì)于出行者信息服務(wù)系統(tǒng)(ATIS)更是不可或缺的一部分。
　　 本文以交通網(wǎng)絡(luò)為研究對(duì)象，研究城市道路交通網(wǎng)絡(luò)在限制條件下的單源最短路徑問題，探求在不同限制條件下最短路徑探索的實(shí)現(xiàn)方法，并基于此方法給出程序

2、實(shí)現(xiàn)。本文涉及的限制條件，不僅包括了道路交通網(wǎng)絡(luò)本身的限制條件(通行限制、轉(zhuǎn)向限制(延誤)以及道路等級(jí)、道路交通狀況)，還包括了面向用戶服務(wù)的可供最短路探索需求者自定義的限制條件(限高、限寬和限載)。
　　 程序所采用的最短路算法是基于鄰接表網(wǎng)絡(luò)存儲(chǔ)結(jié)構(gòu)和單隊(duì)列的程序運(yùn)行結(jié)構(gòu)的Dijkstra算法，程序在實(shí)現(xiàn)上分兩個(gè)部分，程序l用于最短路探索方法的研究，實(shí)現(xiàn)在自建的虛擬路網(wǎng)下的最短路探索，其網(wǎng)絡(luò)的存儲(chǔ)方式為完全意義上的拓?fù)浣Y(jié)構(gòu)存

3、儲(chǔ)，點(diǎn)與邊的關(guān)系在拓?fù)湮募袊?yán)格對(duì)應(yīng)，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生改變時(shí)，必須改變拓?fù)湮募拇鎯?chǔ)才能夠使得最短路探索得以正確執(zhí)行；程序2采用了拓?fù)浯鎯?chǔ)與路徑探索相分離的方式，使得路徑探索可以不完全依賴于拓?fù)浣Y(jié)構(gòu)，當(dāng)實(shí)際路網(wǎng)拓?fù)浣Y(jié)構(gòu)發(fā)生變化的時(shí)候，可以僅僅通過對(duì)路段屬性的調(diào)整來實(shí)現(xiàn)探索過程的變更，同時(shí)程序結(jié)合了GIS二次開發(fā)組件提供的讀取和顯示圖層的功能，開發(fā)了可視化的應(yīng)用程序，將文中所涉及的各種交通網(wǎng)絡(luò)限制條件下的最短路探索一一實(shí)現(xiàn)，并對(duì)其以具備