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 (); privatestaticLinkedList subB=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"}; Set plots=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; privateList vertex;//按顺序保存顶点s privateList edges; publicint[][]getSubTrainMatrix(){ returnsubTrainMatrix; } publicvoidsetVertex(List vertices){ this.vertex=vertices; } publicList getVertex(){ returnvertex; } publicList getEdges(){ 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;i vertices){ 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&&j vertices=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); } privatestaticSubTrainMap graph; /**打印顶点之间的距离*/ publicvoidprintL(int[][]a){ for(inti=0;i vertices=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算法实现。欢迎其他人讨论和提供实现。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。