北京地铁最短路径实现 - 31701002罗灵洁
北京地铁最短路径规划
github地址 github
需求理解
- 将地铁线路保存成一个可读入，简洁明了的文本
- 程序能正确读入这个文件，并获取地铁线路信息
- 程序能正确处理输入的命令行
- 地铁能正确输出指定地铁线经过的站点
- 程序能正确输出两个站点间的最短路径
- 程序要有健壮性，能通过各类性能测试
- 按要求编写博客，详细说明花费时间，代码，各个模块和测试用例
文本存储方式
该文本直接保存进了各条线路的各个站点，没有在文本中考虑换乘点。当读入“一号线”等文字时，将它转换为线路的id号，然后在way数组中作为下标，将后面的各个站点的id号存储进去。换乘情况的话，因为每新读入一个站点，都会给它赋一个id号，所以只要每次判断该站点是否有id号了，如已存在，该站点就是换乘点，保存换乘信息。例如上图中一号线的西单，在四号线中也存在，所以该站点就可以换乘一号线或四号线。
实际所需时间
模块结构
共一个类：Subway
Subway类共有六个函数：
-
public static void searchWay(String name, String args):该函数的目标是用来满足需求二，保存所查询线路的各个站点。name就是通过命令行输入的线路的名称，args就是保存信息的文件名称。
该函数先通过if语句判断来得到线路的id号，然后在way数组下得到各个站点的id号，然后根据id号调用getKey()函数得到站点名称，保存进文件中。 -
public static int findMinDist(int[] dist,int[] collected):该函数的作用是在未被收录的顶站中寻找dist最小的一个站点。
-
public static void dijkstra(String station1,String station2, String baocun)：该函数的算法是采用了dijkstra算法，该算法是先利用上面的findMinDist函数找到距离起点最小的点，然后更新其他点到起点的距离。在更新的过程中，判断了某个站点是否是换乘点，如果是的话，就更新这条路的换乘次数，最后当路径长度一致时，根据换乘次数来选择是哪一条路径，当换乘次数也一致时，就两条路径都输出。判断某个站点是否是换乘点的方法是通过一个二重循环，一个一重循环；先通过二重循环找到当前站点和前一个站点在共同的哪一个线路上，再判断当前站点的前前站点是否在这条线路上，若不在，则说明前一个站点是换乘点，保存信息。
-
public static String getKey(int value):该函数的作用就是通过id号来得到站点的名称；
-
public static void main(String[] args) throws FileNotFoundException：main函数就是处理各种参数，建好map这个表，为每个站点赋好id，为每条线路赋好id号，设置好相邻站点间的距离为1，保存好每条线路上的各个站点。
-
public static void shuchu(int[] dist,int[] path,int[][] exchange,int e,int s,int count,int[] changePoint, String baocun):该函数是用于将最短路径上所经过的站点和在哪个站点换乘几号线的信息保存到文件名问baocun的文件中去；先用wayTo这个数组保存整条路径，然后将wayTo这个数组里的id号和保存的换乘点的id号进行比较，如果该站点是换乘点，就在下一站输出前，输出需要换乘到几号线。
性能改进
- 因为dijkstra算法是将起点到其他每个站点间的最短路径都求出来了，所以会加大运行时间和保存空间，所以在写代码的时候，当有一次点到了我们的终点时，就break。这样只会运行和保存起点到终点的路径，其他站点不需要考虑。
- 因为存在路径长度相同，换乘次数一样的情况，所以两条路径都需要输出，让乘客自主选择，所以会运行保存到文件的代码多次，所以我写了一个函数shuchu，这样只要多次调用一个函数，而不用多次书写同一份代码了。还有根据id号得到名称，也需要多次写同一份代码，所以变成一个函数，多次调用即可。
测试用例
需求一
需求二
需求三
正确性测试
- 十三陵景区 北邵洼（无换乘）
- 十三陵景区 育知路（换乘一次）
- 积水潭 平安里（路径长度一致，换乘次数一样，两条线路一起输出，并且二号线循环）
- 积水潭 苏州街（两次换乘）
- 莲花桥 北京西站（路径长度一致，但换乘次数少）
- 中国美术馆 天安门西（路径长度一致，换乘次数一样，三次，两条线路一起输出）
- 石厂 二号航站楼（超长线路）
- 国贸 高碑店（一号线和八通线）
鲁棒性测试
- 输了三号线：
- 输了不存在的站点
个人总结
这个项目采用java来完成，利用了dijkstra算法。并在原有的基础上进行了修改，在一边计算路径的情况下，一边判断是否换乘了，计算路径的换乘次数，然后选择路径短，换乘次数少的路径。
我写的代码没采用很复杂的方式，也是因为个人能力的不足，也深知还有很多更好的存储的方式，更方便，适宜的算法，但这次项目也进一步锻炼了我前期思考，准备，中期写代码，后期总结的能力。
这次数据的储存我主要采用了数组和map,通过数组来存储某条线路的站点，来存储某个站点可换乘的线路。通过map来存储站点的id号。