狄杰斯特拉算法求地铁最短路径换乘方案（上海地铁为例）

package HRJ; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; public class dijskrat { static List<List<Station>> getAllpath(List<List<dNode>> net, List<Node> stationmap, Map map, String start, String end){ List<Integer> sstation = new ArrayList<>();//出发站点 List<Integer> estation = new ArrayList<>();//终点站 //得到出发的id for(int i = 0; i< map.lines.size(); i++){ for(int j = 0; j<map.lines.get(i).stations.size(); j++){ if(map.lines.get(i).stations.get(j).StaName.equals(start)) sstation.add(map.lines.get(i).stations.get(j).ID-1); if(map.lines.get(i).stations.get(j).line==4 &&map.lines.get(i).stations.get(j).StaName.equals("浦电路")&&start.equals("浦电路4")) sstation.add(map.lines.get(i).stations.get(j).ID-1); if(map.lines.get(i).stations.get(j).line==6 &&map.lines.get(i).stations.get(j).StaName.equals("浦电路")&&start.equals("浦电路6")) sstation.add(map.lines.get(i).stations.get(j).ID-1); if(map.lines.get(i).stations.get(j).StaName.equals(end)) estation.add(map.lines.get(i).stations.get(j).ID-1); if(map.lines.get(i).stations.get(j).line==4 &&map.lines.get(i).stations.get(j).StaName.equals("浦电路")&&end.equals("浦电路4")) estation.add(map.lines.get(i).stations.get(j).ID-1); if(map.lines.get(i).stations.get(j).line==6 &&map.lines.get(i).stations.get(j).StaName.equals("浦电路")&&end.equals("浦电路6")) estation.add(map.lines.get(i).stations.get(j).ID-1); } } Node allpath = new Node(); for(int s = 0;s<sstation.size();s++) { for(int e = 0;e<estation.size();e++){ Graph.updatestationmap(stationmap); Minpath(net, stationmap, map, sstation.get(s), estation.get(e)); stationmap.get(estation.get(e)).pathdelete(); for(int i = 0;i<stationmap.get(estation.get(e)).path.size();i++){ if(!Graph.isexist(stationmap.get(estation.get(e)).path.get(i),allpath.path)) allpath.path.add(stationmap.get(estation.get(e)).path.get(i)); } } } return allpath.path; } //输出线路 static void Printpath(List<List< Station>> path, String[] stations){ int line; for(int i=0;i<path.size();i++){ for(int j = 0;j<path.get(i).size();j++) { if (j == path.get(i).size() - 1) System.out.print(path.get(i).get(j).StaName); else if (j == 0) { line = path.get(i).get(j).line; if (line == 14 || line == 15) line = 10; if (line == 18 || line == 19) line = 11; System.out.print(path.get(i).get(j).StaName); System.out.print("-line" + line + "-"); } else if (Allpath.isIn(stations, path.get(i).get(j))) { line = path.get(i).get(j).line; if (line == 14 || line == 15) line = 10; if (line == 18 || line == 19) line = 11; System.out.print(path.get(i).get(j).StaName); System.out.print("-line " + line + "-"); } else if (j < path.get(i).size() - 1) { int line1 = path.get(i).get(j - 1).line; int line2 = path.get(i).get(j).line; if (line1 == 14 || line1 == 15) line1 = 10; if (line1 == 18 || line1 == 19) line1 = 11; if (line2 == 14 || line2 == 15) line2 = 10; if (line2 == 18 || line2 == 19) line2 = 11; if (line1 != line2){ System.out.print(path.get(i).get(j).StaName); if (j < path.get(i).size() - 1) { System.out.print("-line " + line2 + "-"); } } else if(path.get(i).get(j - 1).line!=path.get(i).get(j).line&& line1==line2 &&path.get(i).get(j - 1).line!=line1&&path.get(i).get(j).line!=line2){ System.out.print(path.get(i).get(j).StaName); if (j < path.get(i).size() - 1) { System.out.print("-line " + line2 + "-"); } } } } System.out.println(); } } //狄杰斯特拉算法计算最短路径 static void Minpath(List<List< dNode>> net, List< Node> stationmap, Map map, int s, int e){ Comparator< Node> com = new Comparator< Node>() { public int compare( Node n1, Node n2){ return n1.time-n2.time; } }; int snode = s; PriorityQueue< Node> unknown = new PriorityQueue<>(com); stationmap.get(s).time = 0; Node Known = stationmap.get(s); for(int i =0 ;i<stationmap.size();i++){ unknown.offer(stationmap.get(i)); } unknown.poll(); while (Known.station.ID!=stationmap.get(e).station.ID){ Known.Add(Known.station); Known.pathdelete(); Known.known = true; snode = Known.station.ID-1; for(int i = 0;i<net.get(snode).size();i++){ if(stationmap.get(net.get(snode).get(i).end-1).known==false){ if(stationmap.get(net.get(snode).get(i).end-1).time >net.get(snode).get(i).time+stationmap.get(net.get(snode).get(i).start-1).time){ stationmap.get(net.get(snode).get(i).end-1).Copy(Known.path); if(stationmap.get(net.get(snode).get(i).end-1).station.StaName.equals(Known.station.StaName)) { stationmap.get(net.get(snode).get(i).end-1).Remove(Known.station);//如果是换乘，就去掉前一个站点 } unknown.remove(stationmap.get(net.get(snode).get(i).end-1)); stationmap.get(net.get(snode).get(i).end-1).time=net.get(snode).get(i).time+stationmap.get(net.get(snode).get(i).start-1).time; unknown.offer(stationmap.get(net.get(snode).get(i).end-1)); } //如果有第二条路 else if (stationmap.get(net.get(snode).get(i).end-1).time ==net.get(snode).get(i).time+stationmap.get(net.get(snode).get(i).start-1).time){ stationmap.get(net.get(snode).get(i).end-1).Add(Known.path); if(stationmap.get(net.get(snode).get(i).end-1).station.StaName.equals(Known.station.StaName)) { stationmap.get(net.get(snode).get(i).end-1).Remove(Known.station); } stationmap.get(net.get(snode).get(i).end-1).pathdelete(); } } } Known = unknown.poll(); } Known.Add(Known.station); } //路线的换乘次数 static int exchangenum(List<Station> path){ int counter = 0; int line = 0; for(int i = 0;i<path.size()-1;i++){ if(path.get(i).line!=line) { counter++; line = path.get(i).line; } } return counter; } }