1.将txt文件保存的地铁线路导入java。
2.输入线路名称，找到线路上所有的站点。
3.输入两个站点，找出两站最短路径。
一号线：李楼 双林 财经大学 ..
二号线：曹庄 卞兴 芥园西道..
三号线：南站 杨伍庄 学府工业园..
..
对地铁地铁观察，地铁站点超过一百个，如选择邻接矩阵，矩阵大小会超过10000,为稀疏表，很浪费存储资源，邻接表只需要存储站点的相邻站点，所占空间较小，所以选择邻接表
为了练习java，选择用java编写。程序需要两个类
1.站点
public class Vertex { public final String name; public ArrayList<Vertex> neighbour; public String line; public Vertex(String name){ this.name = name; neighbour = new ArrayList<Vertex>(); } public String toName(){ return name; } public String toLine(){ return line; } }
2.线路
public class line { public final String name; public List<String> station; //=new ArrayList<String>() public line(String name,List<String> station){ this.name = name; this.station = station; } }
线路保存线上的站点和线路名，站点保存相邻站点，站点名和所属线路。
程序难点为处理换乘点，地铁站换乘点分为三种：
处理三种不同情况的关键是确定站点的相邻点。为处理方便，我将换乘点设为多个变量，让其分属于不同线路。
选择Dijkstra算法
if (index != -1) { st[index] = true; // 更新当前最短路径及距离 for (int w = 0; w < numOfVexs; w++) { if (st[w] == false) { //取确认了最短路径的顶点的连接顶点信息 current = vexs[index].firstadj; while (current != null) { //如果确认的顶点可以到未确认的顶点，则重新计算是否有最短路径 if (current.adjvex == w) { if ((min + current.weight) < distance[w]) { distance[w] = min + current.weight; break; } } current = current.nextadj; } } } }
程序难点为对转站点多种情况的处理，需要在导入txt文件时，生成站点类，这是就要处理好站点类的邻接站点。只是后面最短路径算法的基础。
原文：https://www.cnblogs.com/jgxjav/p/11548346.html