北京地鐵乘坐線路查詢(圖最短路徑).ppt

《北京地鐵乘坐線路查詢(圖最短路徑).ppt》由會員分享，可在線閱讀，更多相關《北京地鐵乘坐線路查詢(圖最短路徑).ppt（14頁珍藏版）》請在裝配圖網上搜索。

June 14th , 2018,北京地鐵乘坐線路查詢,葉靜波,June 14th , 2018,catalogue,問題描述 數據結構設計 數據讀入 算法設計 打印輸出 其他算法 總結,June 14th , 2018,一、問題描述,編寫一個程序實現北京地鐵最短乘坐（站）線路查詢，輸入為起始站名和目的站名，輸出為從起始站到目的站的最短乘坐站換乘線路。,文件bgstations.txt為數據文件，包含了北京地鐵的 所有線路及所有車站信息。其格式如下： 12 1 23 蘋果園 0 古城 0 … 公主墳 1 … 四惠東 1 2 2 19 西直門 1 積水潭 0 … 西直門 說明：表明目前北京地鐵共開通12條線，其中1號線有23個車站，分別 為蘋果園，非換乘站；…； 公主墳，換乘站…。2線共有19個站，分別為西直門，換乘站，…。,,,,站名，是否換乘,線路編號，該線總站數,線路總數,June 14th , 2018,一、問題描述,控制臺輸入,,,,,,,,,,,,,June 14th , 2018,二、數據結構設計,June 14th , 2018,三、數據讀入,可以先控制臺輸入起始站和終點站char name_start[N],name_end[N]; 然后用文件輸入： 初始化圖的權重和線路編號； 輸入線路總數scanf(“%d “, ｝ ｝,可以利用hash優(yōu)化查找,June 14th , 2018,四、算法設計,數組s[NUM]記錄源點v到圖中頂點的最短路徑已經找到。 數組dis[NUM]記錄源點v到圖中頂點的最短路徑的路徑長度。 數組path[NUM] 記錄源點v到圖中頂點的最短路徑所經過的頂點序列。,Dijkstra,初始化三個數組; for( i:0, Vsum-1){ int min=MAX; int v; for( j:0, Vsum){ if (s[j]未標記 記錄前驅路徑 }}},O( ?? 2 ),June 14th , 2018,dist,s,path,0 10 2 ? ? ? ?,1 0 0 0 0 0 0,2,4,13,0 10 ? ?,4,8,10,0 10 2 ?,8,9,15,0 2 4 10,9,0 2 4 8 10 15,10,13,0 9 2 4 8,13,0 9 2 4 8 10,,,,,,,min,四、算法設計,Path[]={1,1,5,1,3,4,4,6},June 14th , 2018,五、打印輸出,路徑追溯,Path[]={1,1,5,1,3,4,4,6},V1=1,V2=7,t=7,棧cout[]={7,6,4,3}，出棧得到{3,4,6,7},7,7,6,4,6,4,3,3,1,t=V1=1,先把路徑追溯回來（棧的思想） last保存上一站，k乘坐站數 出棧得到第一個站u,記錄u與V1的路線L 打印V1名稱，路線編號 last=u； 當棧不為空時循環(huán)｛ u=pop()； if( L!=u與last的路線)｛ 更新L； 打印k，last名稱，更新的路線編號； k=0; ｝ k++; last=u; ｝ 打印k，v2名稱,June 14th , 2018,五、打印輸出,如何輸出換乘信息,,u=知春路，L=10,k=1; 打印“西土城-10(” last=知春路; 循環(huán){ u=大鐘寺; 大鐘寺,知春路的路線13 !=L{ L=13; 打印“1)-知春路-13(” k=0; } k++;last=u; },June 14th , 2018,五、打印輸出,June 14th , 2018,六、其他算法,Floyd,O( ?? 3 ),June 14th , 2018,六、其他算法,廣度優(yōu)先遍歷,從頂點向周圍搜索，不斷更新最短路,O(n* ?? ),June 14th , 2018,七、總結,分析問題，設計合理的數據結構 理解輸入輸出，把數據讀入 找到合適的最短路徑算法（ Dijkstra-較大數據, Floyd-較小數據,廣搜-較大數據……） 求出相應的最短路徑 打印輸出,Thank you!,