北京地鐵乘坐線路查詢(圖最短路徑).ppt
《北京地鐵乘坐線路查詢(圖最短路徑).ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《北京地鐵乘坐線路查詢(圖最短路徑).ppt(14頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
June 14th , 2018,北京地鐵乘坐線路查詢,葉靜波,June 14th , 2018,catalogue,問(wèn)題描述 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 數(shù)據(jù)讀入 算法設(shè)計(jì) 打印輸出 其他算法 總結(jié),June 14th , 2018,一、問(wèn)題描述,編寫一個(gè)程序?qū)崿F(xiàn)北京地鐵最短乘坐(站)線路查詢,輸入為起始站名和目的站名,輸出為從起始站到目的站的最短乘坐站換乘線路。,文件bgstations.txt為數(shù)據(jù)文件,包含了北京地鐵的 所有線路及所有車站信息。其格式如下: 12 1 23 蘋果園 0 古城 0 … 公主墳 1 … 四惠東 1 2 2 19 西直門 1 積水潭 0 … 西直門 說(shuō)明:表明目前北京地鐵共開通12條線,其中1號(hào)線有23個(gè)車站,分別 為蘋果園,非換乘站;…; 公主墳,換乘站…。2線共有19個(gè)站,分別為西直門,換乘站,…。,,,,站名,是否換乘,線路編號(hào),該線總站數(shù),線路總數(shù),June 14th , 2018,一、問(wèn)題描述,控制臺(tái)輸入,,,,,,,,,,,,,June 14th , 2018,二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì),June 14th , 2018,三、數(shù)據(jù)讀入,可以先控制臺(tái)輸入起始站和終點(diǎn)站char name_start[N],name_end[N]; 然后用文件輸入: 初始化圖的權(quán)重和線路編號(hào); 輸入線路總數(shù)scanf(“%d “, } },可以利用hash優(yōu)化查找,June 14th , 2018,四、算法設(shè)計(jì),數(shù)組s[NUM]記錄源點(diǎn)v到圖中頂點(diǎn)的最短路徑已經(jīng)找到。 數(shù)組dis[NUM]記錄源點(diǎn)v到圖中頂點(diǎn)的最短路徑的路徑長(zhǎng)度。 數(shù)組path[NUM] 記錄源點(diǎn)v到圖中頂點(diǎn)的最短路徑所經(jīng)過(guò)的頂點(diǎn)序列。,Dijkstra,初始化三個(gè)數(shù)組; for( i:0, Vsum-1){ int min=MAX; int v; for( j:0, Vsum){ if (s[j]未標(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,先把路徑追溯回來(lái)(棧的思想) 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é),分析問(wèn)題,設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu) 理解輸入輸出,把數(shù)據(jù)讀入 找到合適的最短路徑算法( Dijkstra-較大數(shù)據(jù), Floyd-較小數(shù)據(jù),廣搜-較大數(shù)據(jù)……) 求出相應(yīng)的最短路徑 打印輸出,Thank you!,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 北京地鐵 乘坐 線路 查詢 圖最短 路徑
鏈接地址:http://m.kudomayuko.com/p-1915267.html