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
该特定条件下的实现：
packagecom.patrick.bishi;
importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.Scanner;
importjava.util.Set;
/**
*获取两条地铁线上两点间的最短站点数
*
*@authorpatrick
*
*/
publicclassSubTrain{
privatestaticLinkedListsubA=newLinkedList();
privatestaticLinkedListsubB=newLinkedList();
publicstaticvoidmain(String[]args){
Stringsa[]={"A1","A2","A3","A4","A5","A6","A7","A8","A9",
"T1","A10","A11","A12","A13","T2","A14","A15","A16",
"A17","A18"};
Stringsb[]={"B1","B2","B3","B4","B5","T1","B6","B7","B8",
"B9","B10","T2","B11","B12","B13","B14","B15"};
Setplots=newHashSet();
for(Stringt:sa){
plots.add(t);
subA.add(t);
}
for(Stringt:sb){
plots.add(t);
subB.add(t);
}
Scannerin=newScanner(System.in);
Stringinput=in.nextLine();
Stringtrail[]=input.split("\\s");
Stringsrc=trail[0];
Stringdst=trail[1];
if(!plots.contains(src)||!plots.contains(dst)){
System.err.println("notheseplot!");
return;
}
intlen=getDistance(src,dst);
System.out.printf("Theshortestdistancebetween%sand%sis%d",src,
dst,len);
}
//经过两个换乘站点后的距离
publicstaticintgetDist(Stringsrc,Stringdst){
intlen=0;
intat1t2=getDistOne("T1","T2");
intbt1t2=subB.indexOf("T2")-subB.indexOf("T1")+1;
inta=0;
if(src.equals("T1")){
a=getDistOne(dst,"T2");
len=a+bt1t2-1;//twopartmustmore1
}elseif(src.equals("T2")){
a=getDistOne(dst,"T1");
len=a+bt1t2-1;
}elseif(dst.equals("T1")){
a=getDistOne(src,"T2");
len=a+at1t2-1;
}elseif(dst.equals("T2")){
a=getDistOne(src,"T1");
len=a+at1t2-1;
}
returnlen;
}
//获得一个链表上的两个元素的最短距离
privatestaticintgetDistOne(Stringsrc,Stringdst){
intaPre,aBack,aLen,len,aPos,bPos;
aPre=aBack=aLen=len=0;
aLen=subA.size();
if("T1".equals(src)&&"T2".equals(dst)){
inta=subA.indexOf("T1");
intb=subA.indexOf("T2");
intat1t2=(b-a)>(a+aLen-b)?(a+aLen-b):(b-a);
intbt1t2=subB.indexOf("T2")-subB.indexOf("T1");
len=at1t2>bt1t2?bt1t2:at1t2;
}elseif(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;
}
}elseif(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!");
}
returnlen+1;
}
publicstaticintgetDistance(Stringsrc,Stringdst){
intaPre,aBack,len,aLen;
aPre=aBack=len=aLen=0;
aLen=subA.size();
inta=subA.indexOf("T1");
intb=subA.indexOf("T2");
intat1t2=(b-a)>(a+aLen-b)?(a+aLen-b):(b-a);
intbt1t2=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")){
intt=getDist(src,dst);
len=len>t?t:len;
}
}else{
intat1=getDist(src,"T1");
intat2=getDist(src,"T2");
intbt1=getDist(dst,"T1");
intbt2=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;
inttmp=aBack>aPre?aPre:aBack;
len=len>tmp?tmp:len;
}
returnlen;
}
}
通用乘地铁方案的实现（最短距离利用Dijkstra算法）：
packagecom.patrick.bishi;
importjava.util.ArrayList;
importjava.util.List;
importjava.util.Scanner;
/**
*地铁中任意两点的最有路径
*
*@authorpatrick
*
*/
publicclassSubTrainMap{
protectedint[][]subTrainMatrix;//图的邻接矩阵，用二维数组表示
privatestaticfinalintMAX_WEIGHT=99;//设置最大权值，设置成常量
privateint[]dist;
privateListvertex;//按顺序保存顶点s
privateListedges;
publicint[][]getSubTrainMatrix(){
returnsubTrainMatrix;
}
publicvoidsetVertex(Listvertices){
this.vertex=vertices;
}
publicListgetVertex(){
returnvertex;
}
publicListgetEdges(){
returnedges;
}
publicintgetVertexSize(){
returnthis.vertex.size();
}
publicintvertexCount(){
returnsubTrainMatrix.length;
}
@Override
publicStringtoString(){
Stringstr="邻接矩阵：\n";
intn=subTrainMatrix.length;
for(inti=0;i();
this.subTrainMatrix=newint[size][size];
this.dist=newint[size];
for(inti=0;ivertices){
this.vertex=vertices;
intsize=getVertexSize();
this.subTrainMatrix=newint[size][size];
this.dist=newint[size];
for(inti=0;i边的权值
publicvoidinsertEdge(Tstart,Tstop,intweight){//插入一条边
intn=subTrainMatrix.length;
inti=getPosInvertex(start);
intj=getPosInvertex(stop);
if(i>=0&&i=0&&j=0&&i=0&&jvertices=newArrayList();
vertices.add("A");
vertices.add("B");
vertices.add("C");
vertices.add("D");
vertices.add("E");
graph=newSubTrainMap(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);
}
privatestaticSubTrainMapgraph;
/**打印顶点之间的距离*/
publicvoidprintL(int[][]a){
for(inti=0;ivertices=newArrayList();
for(Stringt:sa){
if(!vertices.contains(t)){
vertices.add(t);
}
}
for(Stringt:sb){
if(!vertices.contains(t)){
vertices.add(t);
}
}
graph=newSubTrainMap(vertices);
for(inti=0;i"+stop+"经过的站点数为："+len);
}
publicintfind(Tstart,Tstop){
intstartPos=getPosInvertex(start);
intstopPos=getPosInvertex(stop);
if(startPos<0||startPos>getVertexSize())
returnMAX_WEIGHT;
String[]path=dijkstra(startPos);
System.out.println("从"+start+"出发到"+stop+"的最短路径为："
+path[stopPos]);
returndist[stopPos];
}
//单元最短路径问题的Dijkstra算法
privateString[]dijkstra(intvertex){
intn=dist.length-1;
String[]path=newString[n+1];//存放从start到其他各点的最短路径的字符串表示
for(inti=0;i<=n;i++)
path[i]=newString(this.vertex.get(vertex)+"-->"
+this.vertex.get(i));
boolean[]visited=newboolean[n+1];
//初始化
for(inti=0;i<=n;i++){
dist[i]=subTrainMatrix[vertex][i];//到各个顶点的距离，根据顶点v的数组初始化
visited[i]=false;//初始化访问过的节点，当然都没有访问过
}
dist[vertex]=0;
visited[vertex]=true;
for(inti=1;i<=n;i++){//将所有的节点都访问到
inttemp=MAX_WEIGHT;
intvisiting=vertex;
for(intj=0;j<=n;j++){
if((!visited[j])&&(dist[j]"+this.vertex.get(j);
}
}//updateallnewdistance
}//visiteallnodes
//for(inti=0;i<=n;i++)
//System.out.println("从"+vertex+"出发到"+i+"的最短路径为："+path[i]);
//System.out.println("=====================================");
returnpath;
}
/**
*图的边
*
*@authorpatrick
*
*/
classEdge{
privateTstart,dest;
privateintweight;
publicEdge(){
}
publicEdge(Tstart,Tdest,intweight){
this.start=start;
this.dest=dest;
this.weight=weight;
}
publicStringtoString(){
return"("+start+","+dest+","+weight+")";
}
}
}
图中各边的权可以是距离也可以是票价，初始化的方案决定实现的目标。最短路径计算也可以用Floyd算法实现。欢迎其他人讨论和提供实现。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。