java实现乘地铁方案的最优选择（票价，距离）

 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 subA = new LinkedList(); private static LinkedList subB = new LinkedList(); 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 plots = new HashSet(); 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 { protected int[][] subTrainMatrix; // 图的邻接矩阵，用二维数组表示 private static final int MAX_WEIGHT = 99; // 设置最大权值，设置成常量 private int[] dist; private List vertex;// 按顺序保存顶点s private List edges; public int[][] getSubTrainMatrix() { return subTrainMatrix; } public void setVertex(List vertices) { this.vertex = vertices; } public List getVertex() { return vertex; } public List 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 (); this.subTrainMatrix = new int[size][size]; this.dist = new int[size]; for (int i = 0; i  vertices) { this.vertex = vertices; int size = getVertexSize(); this.subTrainMatrix = new int[size][size]; this.dist = new int[size]; for (int i = 0; i 边的权值 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 = 0 && j = 0 && i = 0 && j  vertices = new ArrayList(); vertices.add("A"); vertices.add("B"); vertices.add("C"); vertices.add("D"); vertices.add("E"); graph = new SubTrainMap(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 graph; /** 打印顶点之间的距离 */ public void printL(int[][] a) { for (int i = 0; i  vertices = new ArrayList(); 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(vertices); for (int i = 0; i  " + 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] " + 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 + ")"; } } }