北京地铁乘坐线路查询(图最短路径)-1.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_start[N],name_end[N]; 然后用文件输入： 初始化图的权重和线路编号； 输入线路总数scanf(%d ,LINE); 循环｛ 输入线路编号和该路站数scanf(%d %d ,no,sum); 设置标记上一站 last=-1； 循环｛ 输入站名和换乘状态scanf(%s %d ,name,is); /*查找该站是否已存在*/ int index=search(name); 如果不存在｛ 保存该站，记录该站与上一站的线路编号, 并更新last; ｝否则直接记录并更新last; ｝ ｝ 可以利用hash优化查找 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]未标记最短路dis[j]min){ v=j; 记录该点 min=dis[v];保存最短路 ｝ s[v]=1标记； if (v==终点) return; for(j:0,Vsum){ if (!s[j]dis[j]min+i站与j站的距离){ dis[j]= min + i站与j站的距离; path[j]=v; 记录前驱路径 }}} 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； 打