北京地铁最短路径（Java+Dijkstra算法） |
您所在的位置：网站首页 › 北京地铁价格查询系统 › 北京地铁最短路径（Java+Dijkstra算法） |
北京地铁最短路径（Java+Dijkstra算法）
|
接上篇需求分析： https://www.cnblogs.com/Shevewinyei/p/13849379.html 一、算法描述： 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 完整代码的github地址：https://github.com/Shevewinyei/SubwayChange
二、核心代码： public static int Dijkstra(int startId,int endId,int[][] graph,int[] visit,int[] pre) { //节点个数 int n = graph.length; PriorityQueue pq = new PriorityQueue(new Node()); //将起点加入pq pq.add(new Node(startId, 0)); while (!pq.isEmpty()){ Node t = pq.poll(); //当前节点是终点，即可返回最短路径 if(t.node == endId) return t.cost; //t节点表示还未访问 if (visit[t.node]==0){ //将节点设置为已访问 visit[t.node] = -1; //将当前节点相连且未访问的节点遍历 for (int i = 0; i < n; i++) { if (graph[t.node][i]!=0 && visit[i]==0) { pq.add(new Node(i, t.cost + graph[t.node][i])); pre[i] = t.node; } } } } return -1; }三、解题思路：
四、station站点类代码： public class station { String stationName = ""; //站点名称 ArrayList LineID = new ArrayList(); //站点所在的线路 ArrayList AdjacentStations = new ArrayList(); //相邻站点 boolean IsTransfer = false; //站点是否是换乘站 //设置站点名称 public void setName(String name) { this.stationName = name; } //添加站点所在线路信息 public void addLineName(String id) { this.LineID.add(id); //如果站点所在线路出现多条，则可作为换乘点 if(LineID.size()>1) { IsTransfer = true; } } public void addAdjacentStations(station t) { this.AdjacentStations.add(t); } public String getStationName() { return this.stationName; } public ArrayList getLineName() { return this.LineID; } public ArrayList getAdjacentStations(){ return this.AdjacentStations; } public boolean getIsTransfer() { return this.IsTransfer; } }如果觉得代码比较繁琐难读懂，可以直接看下面的图。
五、读取txt文件中的数据，构造包含所用station的集合（不重复）。在读取数据过程中，不断更新邻接矩阵。 / /读取地铁线路数据，创建站点数组 public static void AddStation() throws FileNotFoundException { Scanner in = new Scanner(new File("/Users/shenwenyan/eclipse-workspace/subwayChange/src/SubwayMessage.txt")); while(in.hasNextLine()) { String temp = in.nextLine(); String[] tokens = temp.split(" "); //线路名称 String lineName = tokens[0]; for(int i=1;i |
【本文地址】
今日新闻 |
推荐新闻 |