資料結構課程設計

20. 公交線路上優化路徑的查詢 

問題描寫叙述 

最短路徑問題是圖論中的一個經典問題，當中的Dijkstra算法一直被覺得是圖論中的好算法，但有的時候須要适當的調整Dijkstra算法才幹完畢多種不同的優化路徑的查詢。 

對于某城市的公交線路，乘坐公交的顧客希望在這種線路上實作各種優化路徑的查詢。設該城市的公交線路的輸入格式為： 

線路編号：起始站名(該站坐标)；經過的網站1名(該站坐标)；經過的網站2名(該站坐标)；……；經過的網站n名(該站坐标)；終點站名(該站坐标)。該線路的乘坐價錢。該線路平均經過多少時間來一輛。車速。 

比如：63：A(32,45)；B(76,45)；C(76,90)；……；N(100,100)。1元。5分鐘。1/每分鐘。 

假定線路的乘坐價錢與乘坐站數無關，假定不考慮公交線路在路上的交通阻塞。 

對這種公交線路，須要在其上進行的優化路徑查詢包含：不論什麼兩個網站之間最廉價的路徑；不論什麼兩個網站之間最省時間的路徑等等。 

 基本要求 

① 依據上述公交線路的輸入格式，定義并建立合适的圖模型。 

② 針對上述公交線路，能查詢獲得不論什麼兩個網站之間最廉價的路徑，即輸入站名S，T後，能夠輸出從S到T的最廉價的路徑，輸出格式為：線路x：站名S，…，站名M1；換乘線路x：站名M1，…，站名M2；…；換乘線路x：站名MK，…，站名T。共花費x元。 

③ 針對上述公交線路，能查詢獲得不論什麼兩個網站之間最省時間的路徑（不考慮在中間站等下一輛線路的等待時間），即輸入站名S，T後，能夠輸出從S到T的考慮在中間站等下一輛線路的等待時間的最省時間的路徑，輸出格式為：線路x：站名S，…，站名M1；換乘線路x：站名M1，…，站名M2；…；換乘線路x：站名MK，…，站名T。共花費x時間。 

④ 針對上述公交線路，能查詢獲得不論什麼兩個網站之間最省時間的路徑（要考慮在中間站等下一輛線路的等待時間），即輸入站名S，T後，能夠輸出從S到T的考慮在中間站等下一輛線路的等待時間的最省時間的路徑，輸出格式為：線路x：站名S，…，站名M1；換乘線路x：站名M1，…，站名M2；…；換乘線路x：站名MK，…，站名T。共花費x時間。 

(4) 實作提示 

需深入考慮，應依據不同的應用目标，即不同的優化查詢來建立合适的圖模型。 

github位址：

https://github.com/Findxiaoxun/Busmap

devlog

2014年03月19日 13時57分12秒 正式開始，前兩個問題的算法已經有了頭緒，今天就先把這兩個實作。

還是先考慮下資料的讀入和存儲問題吧。以免後期大修改。

路線用vector，聯通否直接用二維數組,每一個點都标序号

class node應該包括的東西：

網站序列，網站經過的線路号，

class route ：

線路經過的網站

線路車速，價格，

等待的時間。

檔案的操作放到server上。同一時候檔案的處理，對路線等的讀入和初步處理在server上。

採用多線程來計算，同一時候，主意在螢幕提示狀态

結果的儲存格式？選擇的點及用的路線。按順序存儲

2014年03月26日 10時32分08秒 盡管scanner巨慢無比，我還是先選用scanner看看吧http://zhidao.baidu.com/link?url=lQFBknkSa43YWkq8gxWtQfQbdg

DS5raKmZBnqQdgpYdI1XUkv_RrjY97Wf9fjr3taj80DKjJNjs1hkaHZ10wTK

建立一個client來處理吧，先，至于用不用server再說吧，用的話，還須要下載下傳檔案。這樣也行。

進度條先放一放，client載入資料用最後.thread 和runnable的差别http://blog.chinaunix.net/uid-20665441-id-310538.html

檔案的工作放到

僅僅寫本地的！！！

version 0.3

資料格式：

線路号 網站數 站1 x1 y1 站2 x2 y2 站3 x3 y3 站4 x4 y4 ...  價格 周期 車速

搜集資料

2014年04月02日 10時35分05秒 把資料格式定下來，同一時候準備做主界面（開始有個頁面的消失動畫）

version 0.6

更新了主界面。準備今晚先寫算法，然後準備更新的東西。

最省時間的那個算法：

首先先把資料讀入進去。也不要處理。讀入的是每條線路的經過的點，這條線路的價格。等等。然後再循環每條線路，更新經過的點的passRoute,還有就是點與點之間的是否通（後期能夠通過兩個點的共同的路線來确定路線。）

14:46 2014/4/23

version 0.7 完好界面，同一時候測試第一個算法功能

後期目标：接入語音功能，能夠彈出結果的選擇界面

Node:

index:節點序号passRoute[]:經過它的線路号len經過它的線路數量x,y:節點坐标

getPassRoute()擷取通過的線路号

getIndex()擷取節點号

addPassRoute()加入經過的線路，使用者在初始加入線路的時候

Route:

speed:速度index線路号price價格time多長時間來一趟len經過的節點數passNode經過的節點号

addPassNode()加入經過的節點号

getPassNode()擷取該線路的節點集合

getSpeed()擷取速度

getPassNodelen()擷取經過的節點數量

16:37 2014/4/27 抓緊時間完好啊！！！

9:15 2014/5/4 goal：完好測試第一個

version 0.8 檔案讀入結束，界面設計70%，準備開始測試第一個

findbutton按下，直接調用dijkstra的方法

最省時間的：先不考慮換成的車号

全部的點都從1開始！！nodelen有意義

15:56 2014/5/5 version 0.9 debug。。。。

12:24 2014/5/6 version 1.0 正在進行第一個的調試，還是讀入的問題啊！！！

while(scan2.hasNext()){

Route b=new Route();

這裡的b一定要在裡面new啊@@@@@

version 1.1 已經完好了第一個功能。并且測試通過。準備加入第二個算法。

我就鬥膽傳上來了，終于實作的效果非常爛。。。花的時間太少了，倒是資料庫的那個課程設計感覺做的還不錯。javascript:void(0)