資料結構課程設計

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位址：

devlog

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

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

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

class node應該包含的東西：

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

class route ：

線路經過的站點

線路車速，價格，

等待的時間。

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

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

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

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

ds5rakmzbnqqdgpydi1xukv_rrjy97wf9fjr3taj80dkjjnjs1hkahz10wtk

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

進度條：http://blog.csdn.net/kakashi8841/article/details/6388797

http://bbs.csdn.net/topics/340076988

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

檔案的工作放到

rmi傳輸檔案：http://www.cnblogs.com/qytan36/archive/2010/03/28/1698885.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%，準備開始測試第一個

find按鈕按下，直接調用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 已經完善了第一個功能。而且測試通過。準備添加第二個算法。

我就鬥膽傳上來了，最終實作的效果很爛。。。花的時間太少了，倒是資料庫的那個課程設計感覺做的還不錯。