java如何實現乘地鐵方案的最優(yōu)選擇功能

這篇文章將為大家詳細講解有關java如何實現乘地鐵方案的最優(yōu)選擇功能，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

初始問題描述：

已知2條地鐵線路，其中A為環(huán)線，B為東西向線路，線路都是雙向的。經過的站點名分別如下，兩條線交叉的換乘點用T1、T2表示。編寫程序，任意輸入兩個站點名稱，輸出乘坐地鐵最少需要經過的車站數量（含輸入的起點和終點，換乘站點只計算一次）。

地鐵線A（環(huán)線）經過車站：A1A2A3A4A5A6A7A8A9T1A10A11A12A13T2A14A15A16A17A18

地鐵線B（直線）經過車站：B1B2B3B4B5T1B6B7B8B9B10T2B11B12B13B14B15

該特定條件下的實現：

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;// 按順序保存頂點sprivate 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;} @Overridepublic 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 + "出發(fā)到" + 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;// 初始化訪問過的節(jié)點，當然都沒有訪問過} dist[vertex] = 0;visited[vertex] = true; for (int i = 1; i <= n; i++) {// 將所有的節(jié)點都訪問到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; // 將距離最近的節(jié)點加入已訪問列表中for (int j = 0; j <= n; j++) {// 重新計算其他節(jié)點到指定頂點的距離if (visited[j]) {continue;}int newdist = dist[visiting] + subTrainMatrix[visiting][j];// 新路徑長度，經過visiting節(jié)點的路徑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 + "出發(fā)到" + 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如何實現乘地鐵方案的最優(yōu)選擇功能”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。