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

June 14th , 2018,北京地鐵乘坐線路查詢,葉靜波,June 14th , 2018,catalogue,問題描述 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 數(shù)據(jù)讀入 算法設(shè)計(jì) 打印輸出 其他算法 總結(jié),June 14th , 2018,一、問題描述,編寫一個(gè)程序?qū)崿F(xiàn)北京地鐵最短乘坐（站）線路查詢，輸入為起始站名和目的站名，輸出為從起始站到目的站的最短乘坐站換乘線路。,文件bgstations.txt為數(shù)據(jù)文件，包含了北京地鐵的 所有線路及所有車站信息。其格式如下： 12 1 23 蘋果園 0 古城 0 公主墳 1 四惠東 1 2 2 19 西直門 1 積水潭 0 西直門 說明：表明目前北京地鐵共開通12條線，其中1號(hào)線有23個(gè)車站，分別 為蘋果園，非換乘站； 公主墳，換乘站。2線共有19個(gè)站，分別為西直門，換乘站，。,站名，是否換乘,線路編號(hào)，該線總站數(shù),線路總數(shù),June 14th , 2018,一、問題描述,控制臺(tái)輸入,June 14th , 2018,二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì),June 14th , 2018,三、數(shù)據(jù)讀入,可以先控制臺(tái)輸入起始站和終點(diǎn)站char name_startN,name_endN; 然后用文件輸入： 初始化圖的權(quán)重和線路編號(hào)； 輸入線路總數(shù)scanf(“%d “, ,可以利用hash優(yōu)化查找,June 14th , 2018,四、算法設(shè)計(jì),數(shù)組sNUM記錄源點(diǎn)v到圖中頂點(diǎn)的最短路徑已經(jīng)找到。 數(shù)組disNUM記錄源點(diǎn)v到圖中頂點(diǎn)的最短路徑的路徑長(zhǎng)度。 數(shù)組pathNUM 記錄源點(diǎn)v到圖中頂點(diǎn)的最短路徑所經(jīng)過的頂點(diǎn)序列。,Dijkstra,初始化三個(gè)數(shù)組; for( i:0, Vsum-1) int min=MAX; int v; for( j:0, Vsum) if (sj未標(biāo)記 記錄前驅(qū)路徑 ,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,四、算法設(shè)計(jì),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乘坐站數(shù) 出棧得到第一個(gè)站u,記錄u與V1的路線L 打印V1名稱，路線編號(hào) last=u； 當(dāng)棧不為空時(shí)循環(huán) u=pop()； if( L!=u與last的路線) 更新L； 打印k，last名稱，更新的路線編號(hào)； 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)先遍歷,從頂點(diǎn)向周圍搜索，不斷更新最短路,O(n* ),June 14th , 2018,七、總結(jié),分析問題，設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu) 理解輸入輸出，把數(shù)據(jù)讀入 找到合適的最短路徑算法（ Dijkstra-較大數(shù)據(jù), Floyd-較小數(shù)據(jù),廣搜-較大數(shù)據(jù)） 求出相應(yīng)的最短路徑 打印輸出,Thank you!,