Shulou(Shulou.com)06/03 Report--

This article will explain to you in detail how to achieve the optimal selection function of the subway scheme by java. The editor thinks it is very practical, so I share it with you for reference. I hope you can get something after reading this article.

Initial problem description:

Two subway lines are known, of which An is a loop line and B is an east-west line, all of which are two-way. The names of the stations passed are as follows, and the transfer points at the intersection of the two lines are indicated by T1 and T2. Write a program, arbitrarily enter two station names, output the minimum number of stations to take the subway (including the input starting point and end point, the transfer station is calculated only once).

Subway line A (ring line) passes through the station: A1A2A3A4A5A6A7A8A9T1A10A11A12A13T2A14A15A16A17A18

Subway line B (straight line) passes through the station: B1B2B3B4B5T1B6B7B8B9B10T2B11B12B13B14B15

The implementation under this particular condition:

Package com.patrick.bishi; import java.util.HashSet;import java.util.LinkedList;import java.util.Scanner;import java.util.Set; / * get the minimum number of stations between two points on two subway lines * * @ 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);} / / the distance after passing through two transfer stations public static int getDist (String src, String dst) {int len = 0 int len at1t2 = getDistOne ("T1", "T2"); int bt1t2 = subB.indexOf ("T2")-subB.indexOf ("T1") + 1 tint a = 0t if (src.equals ("T1")) {a = getDistOne (dst, "T2") Len = a + bt1t2-1 racket / 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 } / / get the shortest distance private static int getDistOne (String src, String dst) {int aPre, aBack, aLen, len, aPos, bPos;aPre = aBack = aLen = len = 0 aBack Len = 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 = aLen = 0X 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 politics aBack = at2 + bt2-1 political len = aBack > aPre? APre: aBack;aPre = at1t2 + at1 + bt2-2 * a back = bt1t2 + at2 + bt1-2 * * int tmp = aBack > aPre? APre: aBack;len = len > tmp? Tmp: len;} return len;}} implementation of universal subway ride scheme (shortest distance using Dijkstra algorithm): package com.patrick.bishi; import java.util.ArrayList;import java.util.List;import java.util.Scanner; / * the most available path of any two points in the subway * * @ author patrick * / public class SubTrainMap {protected int [] [] subTrainMatrix; / / the adjacency matrix of the graph, private static final int MAX_WEIGHT = 99 is represented by a two-dimensional array / / set the maximum weight to a constant private int [] dist;private List vertex;// to save vertices in order: sprivate 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 } @ Overridepublic String toString () {String str = "adjacency matrix:\ 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();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 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];} // 返边的权值 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 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 < 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 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 < 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 + " ->

The number of sites passed by "+ stop +" is: "+ 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 (the shortest path from "+ start +" to "+ stop +" is: "+ path [stopPos]); return dist [stopPos];} / Dijkstra algorithm private String [] dijkstra (int vertex) {int n = dist.length-1 string [] path = new String [n + 1] for unit shortest path problem / / the string that stores the shortest path from start to other points represents for (int I = 0; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.