地铁线路规划——简单分析
? ? ? ? 计算地铁线路最短路径我们要将地铁线路信息等用一个文本文件的形式保存起来,应保存的信息应包括地铁线路名称、各个地铁站点的名称以及车站换乘信息,使得应用程序可以通过读取这个文件,就能掌握关于北京地铁线路的所有信息。 需求1: java subway -map subway.txt
需求2: 现在程序里已经与地铁文件解耦了,那么我们就可以在这个的基础上做一些基础的查询操作。比如说,用户希望查询指定地铁线经过的站点。这样,在应用程序需要支持一个新的命令行参数? java subway -a 1号线 -map subway.txt -o station.txt
需求3: 如果用户希望坐地铁,他希望能通过最少的站数从出发点到达目的地,这样就可以在命令行中以 -b 参数加两个地铁站点名称分别作为出发与目的,比如用户希望知道 洪湖里 到复兴路 之间的最短路线是怎样的,他就可以使用如下命令让程序将结果写入 routine.txt 中。 subway.exe -b 洪湖里 复兴路 -map subway.txt -o routine.txt
你的程序将计算从出发到目的站点之间的最短(经过的站点数最少)路线,并输出经过的站点的个数和路径(包括出发与目的站点)。注意,如果需要换乘,请在换乘站的下一行输出换乘的线路。上面样例的输出就会存入 routine.txt 文件中,文件内容如下: 3 洪湖里 西站 6号线 复兴路 值得注意的是,请严格按照要求输出,不要增加任何额外输出或提示语。 ? 问题分析:其实就是在无向图中求两个节点间的最短路径。 ? 思路:Dijkstra算法步骤如下 ? ?1:遍历所有节点找到未访问过的节点中累积权值(其实就是从源节点到当前节点的路径值和)最小的(设为A)。 ? ?2:遍历该节点所有可达边(连通到目标节点B),如果节点A累积权值加可达边权值小于目标节点B自身的累积权值,则对目标节点B进行更新。 ? ?3:将节点A设定为已访问。 ? ?4:重复(1)直到所有节点均访问完毕。 Dijkstra算法链接:https://blog.csdn.net/jy7788/article/details/45867577 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |