北京地铁乘坐线路查询(图最短路径).ppt

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_startN,name_endN; 然后用文件输入： 初始化图的权重和线路编号； 输入线路总数scanf(“%d “, ,可以利用hash优化查找,June 14th , 2018,四、算法设计,数组sNUM记录源点v到图中顶点的最短路径已经找到。 数组disNUM记录源点v到图中顶点的最短路径的路径长度。 数组pathNUM 记录源点v到图中顶点的最短路径所经过的顶点序列。,Dijkstra,初始化三个数组; for( i:0, Vsum-1) int min=MAX; int v; for( j:0, Vsum) if (sj未标记 记录前驱路径 ,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； 当栈不为空时循环 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=知春路; 循环 u=大钟寺; 大钟寺,知春路的路线13 !=L L=13; 打印“1)-知春路-13(” k=0; k+;last=u; ,June 14th , 2018,五、打印输出,June 14th , 2018,六、其他算法,Floyd,O( 3 ),June 14th , 2018,六、其他算法,广度优先遍历,从顶点向周围搜索，不断更新最短路,O(n* ),June 14th , 2018,七、总结,分析问题，设计合理的数据结构 理解输入输出，把数据读入 找到合适的最短路径算法（ Dijkstra-较大数据, Floyd-较小数据,广搜-较大数据） 求出相应的最短路径 打印输出,Thank you!,