您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇文章主要介绍如何使用java实现乘地铁方案的最优选择,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
初始问题描述:
已知2条地铁线路,其中A为环线,B为东西向线路,线路都是双向的。经过的站点名分别如下,两条线交叉的换乘点用T1、T2表示。编写程序,任意输入两个站点名称,输出乘坐地铁最少需要经过的车站数量(含输入的起点和终点,换乘站点只计算一次)。
地铁线A(环线)经过车站:A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18
地铁线B(直线)经过车站:B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10 T2 B11 B12 B13 B14 B15
该特定条件下的实现:
package com.patrick.bishi; import java.util.HashSet; import java.util.LinkedList; import java.util.Scanner; import java.util.Set; /** * 获取两条地铁线上两点间的最短站点数 * * @author patrick * */ public class SubTrain { private static LinkedList<String> subA = new LinkedList<String>(); private static LinkedList<String> subB = new LinkedList<String>(); public static void main(String[] args) { String sa[] = { "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "T1", "A10", "A11", "A12", "A13", "T2", "A14", "A15", "A16", "A17", "A18" }; String sb[] = { "B1", "B2", "B3", "B4", "B5", "T1", "B6", "B7", "B8", "B9", "B10", "T2", "B11", "B12", "B13", "B14", "B15" }; Set<String> plots = new HashSet<String>(); for (String t : sa) { plots.add(t); subA.add(t); } for (String t : sb) { plots.add(t); subB.add(t); } Scanner in = new Scanner(System.in); String input = in.nextLine(); String trail[] = input.split("\\s"); String src = trail[0]; String dst = trail[1]; if (!plots.contains(src) || !plots.contains(dst)) { System.err.println("no these plot!"); return; } int len = getDistance(src, dst); System.out.printf("The shortest distance between %s and %s is %d", src, dst, len); } // 经过两个换乘站点后的距离 public static int getDist(String src, String dst) { int len = 0; int at1t2 = getDistOne("T1", "T2"); int bt1t2 = subB.indexOf("T2") - subB.indexOf("T1") + 1; int a = 0; if (src.equals("T1")) { a = getDistOne(dst, "T2"); len = a + bt1t2 - 1;// two part must more 1 } else if (src.equals("T2")) { a = getDistOne(dst, "T1"); len = a + bt1t2 - 1; } else if (dst.equals("T1")) { a = getDistOne(src, "T2"); len = a + at1t2 - 1; } else if (dst.equals("T2")) { a = getDistOne(src, "T1"); len = a + at1t2 - 1; } return len; } // 获得一个链表上的两个元素的最短距离 private static int getDistOne(String src, String dst) { int aPre, aBack, aLen, len, aPos, bPos; aPre = aBack = aLen = len = 0; aLen = subA.size(); if ("T1".equals(src) && "T2".equals(dst)) { int a = subA.indexOf("T1"); int b = subA.indexOf("T2"); int at1t2 = (b - a) > (a + aLen - b) ? (a + aLen - b) : (b - a); int bt1t2 = subB.indexOf("T2") - subB.indexOf("T1"); len = at1t2 > bt1t2 ? bt1t2 : at1t2; } else if (subA.contains(src) && subA.contains(dst)) { aPos = subA.indexOf(src); bPos = subA.indexOf(dst); if (aPos > bPos) { aBack = aPos - bPos; aPre = aLen - aPos + bPos; len = aBack > aPre ? aPre : aBack; } else { aPre = bPos - aPos; aBack = aLen - bPos + aPos; len = aBack > aPre ? aPre : aBack; } } else if (subB.contains(src) && subB.contains(dst)) { aPos = subB.indexOf(src); bPos = subB.indexOf(dst); len = aPos > bPos ? (aPos - bPos) : (bPos - aPos); } else { System.err.println("Wrong!"); } return len + 1; } public static int getDistance(String src, String dst) { int aPre, aBack, len, aLen; aPre = aBack = len = aLen = 0; aLen = subA.size(); int a = subA.indexOf("T1"); int b = subA.indexOf("T2"); int at1t2 = (b - a) > (a + aLen - b) ? (a + aLen - b) : (b - a); int bt1t2 = subB.indexOf("T2") - subB.indexOf("T1"); if ((subA.contains(src) && subA.contains(dst)) || (subB.contains(src) && subB.contains(dst))) { len = getDistOne(src, dst); if (src.equals("T1") || src.equals("T2") || dst.equals("T1") || dst.equals("T2")) { int t = getDist(src, dst); len = len > t ? t : len; } } else { int at1 = getDist(src, "T1"); int at2 = getDist(src, "T2"); int bt1 = getDist(dst, "T1"); int bt2 = getDist(dst, "T2"); aPre = at1 + bt1 - 1; aBack = at2 + bt2 - 1; len = aBack > aPre ? aPre : aBack; aPre = at1t2 + at1 + bt2 - 2; aBack = bt1t2 + at2 + bt1 - 2; int tmp = aBack > aPre ? aPre : aBack; len = len > tmp ? tmp : len; } return len; } } 通用乘地铁方案的实现(最短距离利用Dijkstra算法): package com.patrick.bishi; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 地铁中任意两点的最有路径 * * @author patrick * */ public class SubTrainMap<T> { protected int[][] subTrainMatrix; // 图的邻接矩阵,用二维数组表示 private static final int MAX_WEIGHT = 99; // 设置最大权值,设置成常量 private int[] dist; private List<T> vertex;// 按顺序保存顶点s private List<Edge> edges; public int[][] getSubTrainMatrix() { return subTrainMatrix; } public void setVertex(List<T> vertices) { this.vertex = vertices; } public List<T> getVertex() { return vertex; } public List<Edge> getEdges() { return edges; } public int getVertexSize() { return this.vertex.size(); } public int vertexCount() { return subTrainMatrix.length; } @Override public String toString() { String str = "邻接矩阵:\n"; int n = subTrainMatrix.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) str += this.subTrainMatrix[i][j] == MAX_WEIGHT ? " $" : " " + this.subTrainMatrix[i][j]; str += "\n"; } return str; } public SubTrainMap(int size) { this.vertex = new ArrayList<T>(); this.subTrainMatrix = new int[size][size]; this.dist = new int[size]; for (int i = 0; i < size; i++) { // 初始化邻接矩阵 for (int j = 0; j < size; j++) { this.subTrainMatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT;// 无向图 } } } public SubTrainMap(List<T> vertices) { this.vertex = vertices; int size = getVertexSize(); this.subTrainMatrix = new int[size][size]; this.dist = new int[size]; for (int i = 0; i < size; i++) { // 初始化邻接矩阵 for (int j = 0; j < size; j++) { this.subTrainMatrix[i][j] = (i == j) ? 0 : MAX_WEIGHT; } } } /** * 获得顶点在数组中的位置 * * @param s * @return */ public int getPosInvertex(T s) { return vertex.indexOf(s); } public int getWeight(T start, T stop) { int i = getPosInvertex(start); int j = getPosInvertex(stop); return this.subTrainMatrix[i][j]; } // 返<vi,vj>边的权值 public void insertEdge(T start, T stop, int weight) { // 插入一条边 int n = subTrainMatrix.length; int i = getPosInvertex(start); int j = getPosInvertex(stop); if (i >= 0 && i < n && j >= 0 && j < n && this.subTrainMatrix[i][j] == MAX_WEIGHT && i != j) { this.subTrainMatrix[i][j] = weight; this.subTrainMatrix[j][i] = weight; } } public void addEdge(T start, T dest, int weight) { this.insertEdge(start, dest, weight); } public void removeEdge(String start, String stop) { // 删除一条边 int i = vertex.indexOf(start); int j = vertex.indexOf(stop); if (i >= 0 && i < vertexCount() && j >= 0 && j < vertexCount() && i != j) this.subTrainMatrix[i][j] = MAX_WEIGHT; } @SuppressWarnings("unused") private static void newGraph() { List<String> vertices = new ArrayList<String>(); vertices.add("A"); vertices.add("B"); vertices.add("C"); vertices.add("D"); vertices.add("E"); graph = new SubTrainMap<String>(vertices); graph.addEdge("A", "B", 5); graph.addEdge("A", "D", 2); graph.addEdge("B", "C", 7); graph.addEdge("B", "D", 6); graph.addEdge("C", "D", 8); graph.addEdge("C", "E", 3); graph.addEdge("D", "E", 9); } private static SubTrainMap<String> graph; /** 打印顶点之间的距离 */ public void printL(int[][] a) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length; j++) { System.out.printf("%4d", a[i][j]); } System.out.println(); } } public static void main(String[] args) { // newGraph(); String sa[] = { "A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "T1", "A10", "A11", "A12", "A13", "T2", "A14", "A15", "A16", "A17", "A18" }; String sb[] = { "B1", "B2", "B3", "B4", "B5", "T1", "B6", "B7", "B8", "B9", "B10", "T2", "B11", "B12", "B13", "B14", "B15" }; List<String> vertices = new ArrayList<String>(); for (String t : sa) { if (!vertices.contains(t)) { vertices.add(t); } } for (String t : sb) { if (!vertices.contains(t)) { vertices.add(t); } } graph = new SubTrainMap<String>(vertices); for (int i = 0; i < sa.length - 1; i++) graph.addEdge(sa[i], sa[i + 1], 1); graph.addEdge(sa[0], sa[sa.length - 1], 1); for (int i = 0; i < sb.length - 1; i++) graph.addEdge(sb[i], sb[i + 1], 1); Scanner in = new Scanner(System.in); System.out.println("请输入起始站点:"); String start = in.nextLine().trim(); System.out.println("请输入目标站点:"); String stop = in.nextLine().trim(); if (!graph.vertex.contains(start) || !graph.vertex.contains(stop)) { System.out.println("地图中不包含该站点!"); return; } int len = graph.find(start, stop) + 1;// 包含自身站点 System.out.println(start + " -> " + stop + " 经过的站点数为: " + len); } public int find(T start, T stop) { int startPos = getPosInvertex(start); int stopPos = getPosInvertex(stop); if (startPos < 0 || startPos > getVertexSize()) return MAX_WEIGHT; String[] path = dijkstra(startPos); System.out.println("从" + start + "出发到" + stop + "的最短路径为:" + path[stopPos]); return dist[stopPos]; } // 单元最短路径问题的Dijkstra算法 private String[] dijkstra(int vertex) { int n = dist.length - 1; String[] path = new String[n + 1]; // 存放从start到其他各点的最短路径的字符串表示 for (int i = 0; i <= n; i++) path[i] = new String(this.vertex.get(vertex) + "-->" + this.vertex.get(i)); boolean[] visited = new boolean[n + 1]; // 初始化 for (int i = 0; i <= n; i++) { dist[i] = subTrainMatrix[vertex][i];// 到各个顶点的距离,根据顶点v的数组初始化 visited[i] = false;// 初始化访问过的节点,当然都没有访问过 } dist[vertex] = 0; visited[vertex] = true; for (int i = 1; i <= n; i++) {// 将所有的节点都访问到 int temp = MAX_WEIGHT; int visiting = vertex; for (int j = 0; j <= n; j++) { if ((!visited[j]) && (dist[j] < temp)) { temp = dist[j]; visiting = j; } } visited[visiting] = true; // 将距离最近的节点加入已访问列表中 for (int j = 0; j <= n; j++) {// 重新计算其他节点到指定顶点的距离 if (visited[j]) { continue; } int newdist = dist[visiting] + subTrainMatrix[visiting][j];// 新路径长度,经过visiting节点的路径 if (newdist < dist[j]) { // dist[j] 变短 dist[j] = newdist; path[j] = path[visiting] + "-->" + this.vertex.get(j); } }// update all new distance }// visite all nodes // for (int i = 0; i <= n; i++) // System.out.println("从" + vertex + "出发到" + i + "的最短路径为:" + path[i]); // System.out.println("====================================="); return path; } /** * 图的边 * * @author patrick * */ class Edge { private T start, dest; private int weight; public Edge() { } public Edge(T start, T dest, int weight) { this.start = start; this.dest = dest; this.weight = weight; } public String toString() { return "(" + start + "," + dest + "," + weight + ")"; } } }
以上是“如何使用java实现乘地铁方案的最优选择”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。