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<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 + ")";		} 	} }