铁路查询系统的最短路径算法（迪杰斯特拉算法）———————目前尚有bug（溢出的问题）
int startId = findStationIndex(station1);
int endId = findStationIndex(station2);
List<TotalStation_plus> list = new ArrayList<>();
for (int i = 1; i <= 2; i++) {
List<TotalStation_plus> temp = webmapper.research3(i);
AddStation(temp);
}
int[] visit = new int[Max];
int dis=Dijkstra(startId,endId,edges,visit,pre);
List<String> station=PrintPath(startId,endId);
return station;
}
public static void AddStation(List<TotalStation_plus> temp) {
String[] tokens = new String[20];
//将temp集合里的数据存到字符串数组里
for (int i = 0; i < 17; i++) {
tokens[i] = String.valueOf(temp.get(i));
}
//取出线路号
String lineName = tokens[1];
//将一条线存入stations里
for (int i = 2; i < tokens.length; i++) {
//先搜索list中是否存在该站点名称,则只添加线路和相邻节点(去重)
boolean t = false; //判断是否存在arraylist中
for (int j = 0; j < stations.size() - 1; j++) {
if (stations.get(j).getStationName().equals(tokens[i])) {
stations.get(j).addLineName(lineName);
station a = new station();
a.setName(tokens[i + 1]);
a.addLineName(lineName);
stations.add(a);
t = true;
break;
}
}
if (t == false) {
station a = new station();
a.setName(tokens[i]);
a.addLineName(lineName);
stations.add(a);
}
}
//添加相邻站点
for (int i = 1; i < tokens.length - 1; i++) {
ADDAdjacentStations(tokens[i], tokens[i + 1]);
}
}
public static void ADDAdjacentStations(String name1, String name2) {
station t1 = findStation(name1);
station t2 = findStation(name2);
if (t1 != null && t2 != null) {
t1.addAdjacentStations(t2);
t2.addAdjacentStations(t1);
int x = findStationIndex(name1);
int y = findStationIndex(name2);
edges[x][y] = 1;
edges[y][x] = 1;
} else {
//System.out.println("未找到该名称的站点！！！"); }
}
//找到节点
public static station findStation(String name) {
station aStation = null;
for (int i = 0; i < stations.size() - 1; i++) {
if (stations.get(i).getStationName().equals(name)) {
aStation = stations.get(i);
return aStation;
}
}
//System.out.println("未找到该名称的站点！！！");
return aStation;
}
//找到节点下标
public static int findStationIndex(String name) {
int index = -1;
for (int i = 0; i < stations.size() - 1; i++) {
if (stations.get(i).getStationName().equals(name)) {
return i;
}
}
//System.out.println("未找到该名称的站点！！！");
return index;
}
public static int Dijkstra(int startId, int endId, int[][] graph, int[] visit, int[] pre) {
//节点个数
int n = graph.length;
PriorityQueue<Node> 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;
}
//打印路径
public static List<String > PrintPath(int startId, int endId) {
List<String> station=new ArrayList<>();
Stack<Integer> Path = new Stack<Integer>();
int end = endId;
//前置节点入栈，使得输出时候为正序
while (endId != startId) {
Path.add(endId);
int temp = pre[endId];
endId = temp;
}// String routine="";
String lineString = "";
String nextLineString = "";
lineString = IsinOneLine(stations.get(startId), stations.get(Path.peek()));
System.out.println(stations.get(startId).getStationName() + lineString);
int i;
while (true) {
i = Path.pop();
if (Path.isEmpty()) break;
nextLineString = IsinOneLine(stations.get(i), stations.get(Path.peek()));
//判断是否换线
if (nextLineString.equals(lineString)) {
//不换线
System.out.print(" ");
System.out.print("------->");
System.out.println(stations.get(i).getStationName());
station.add(stations.get(i).getStationName());
} else {
//换线
lineString = nextLineString;
System.out.print(" ");
System.out.print("------->");
System.out.println(stations.get(i).getStationName());
System.out.println("在 " + stations.get(i).getStationName() + " 换乘 " + lineString);
station.add(stations.get(i).getStationName() + " 换乘 " + lineString);
}
}
System.out.print(" ");
System.out.print("------->");
System.out.println(stations.get(end).getStationName());
station.add(stations.get(end).getStationName());
return station;
}
//判断是否在同一线路上，如果是就返回线路，否则返回null
public static String IsinOneLine(station a, station b) {
for (int i = 0; i < a.getLineName().size(); i++) {
for (int j = 0; j < b.getLineName().size(); j++) {
if (a.getLineName().get(i).equals(b.getLineName().get(j))) {
return a.getLineName().get(i);
}
}
}
return null;
}
标签：总结,get,int,stations,System,3.16,station,双人,out From： https://www.cnblogs.com/jy-all-bug/p/17224548.html