leastchange.java

一次数据结构的课程设计

// path.java
// demonstrates shortest path with weighted, directed graphs
// to run this program: C>java PathApp
package src;

class leastChange
   {
   private String[] result;
   private final int MAX_VERTS = 20;
   private final int INFINITY = 1000000;
   private int shortnumber = 0;//最少路径中顶点的个数
  // private Vertex vertexList[]; // list of vertices
 //  private Edge edgeList[][];
 //  private int adjMat[][];      // adjacency matrix
  private int shorestMat[][][];  // the matrix which contain the vertexs of the shortest path
   private int nVerts;          // current number of vertices
   private int shortVerts;      //the verts of the shortest path
   private boolean visited[]; //whether the verts have been visted
   private int shortp[]; //储存一条最短路径的所有顶点的编号
  public int flag;
// -------------------------------------------------------------



  public leastChange()               // constructor
      {
	  flag = 0;
	  result = new String[MAX_VERTS];
      visited = new boolean[MAX_VERTS];
      shortp = new int[MAX_VERTS];
      shorestMat = new int[MAX_VERTS][MAX_VERTS][MAX_VERTS];
      nVerts = 0;

      for(int j=0; j<MAX_VERTS; j++)     // set adjacency
				visited[j] = false;
      }  // end constructor
 public boolean setNum(int n)
 {
	 nVerts = n;
	 return true;
 }
 public boolean setShorestMat(int n[][][])
 {
	 shorestMat = n;
	 //for(int i=0; i<nVerts; i++)
	 //  System.out.print(shorestMat[1][3][i]);
	 return true;
 }
   public void path(int start, int stop,Graph g)                // find all shortest paths
      {
		// nVerts = 5;

		  for(shortVerts = 0; shortVerts < nVerts; shortVerts++)
			  for (int i = 0; i < nVerts; i++)
			  	for( int j = 0; j < nVerts; j++)
			  	{
					//如果有更短的路径
					if (g.adjMat[i][shortVerts] + g.adjMat[shortVerts][j] <= g.adjMat[i][j] )
					{
						g.adjMat[i][j] =  g.adjMat[i][shortVerts] + g.adjMat[shortVerts][j];

						//找到使路径变短的点
						for (int m = 0; m < nVerts; m++)
						{
							//如果找到了就覆盖
							if (shorestMat[i][j][m] == shortVerts)
							{
								shorestMat[i][j][m] = -1;
							}
						 }
                            //去掉重复的
						     for (int x = 0; x < nVerts; x++)
								for (int y = 0;y < nVerts; y++)
								{
									if (shorestMat[i][j][x] == shorestMat[i][shortVerts][y])
									     shorestMat[i][shortVerts][y] = -1;
								}

							int n = 0;
							//将更前面的点给最短路径
							for (int k = 0; k < nVerts; k++)
								for (;n < nVerts; n++)//一直找出所有不为-1的点
								{
									if (shorestMat[i][j][k] == -1)
									{
										if (shorestMat[i][shortVerts][n]!= -1)
										      shorestMat[i][j][k] = shorestMat[i][shortVerts][n];
									}
									else
										break;
								}
						   }
					 	}

		if (g.adjMat[start][stop] == INFINITY)
		{
			result[flag] = new String("两城市不相连");
			flag++;
		}
		 else{
			 //return true;
				//System.out.println("最少转车次数:" + (g.adjMat[start][stop] - 1));
 		        displayPaths(start,stop,g);          // display contents
				result[flag] = new String("\n最少转车次数:" + (g.adjMat[start][stop] - 1));
				flag++;
 			}

	}
// -------------------------------------------------------------
//递归列出所有经过的节点
   public void  displayPaths(int start,int stop,Graph g)
      {
	   //String[] stringInfo;
	   //stringInfo = null;

		  visited[start] = true;
		  shortp[shortnumber++] = start;//开始点

		  int v = 0;
		  //一直往下走找到
		 for (int i = 0; i < nVerts; i++)
		 {
			 //System.out.print("两城市"+shorestMat[start][stop][i]);
			 if (shorestMat[start][stop][i] != -1)
			 {
			     v = shorestMat[start][stop][i];
			     shortp[shortnumber++] = v;//第二个点

			     if (!visited[v])
			     {
			  		visited[v]=true;
			  		search(v,stop,g);
			  	    shortnumber--;
		          }
			 }
		  }
	 }


	 public void search(int v,int stop,Graph g){

	 		  visited[v]=true;
	 		  visited[stop]=false;

	 		  if (v == stop) {
				  result[flag] = new String("一种走法:\n");
				  flag++;
	 		   // 打印路径
	 		    for (int x = 0; x < shortnumber-1; x++)
	 		    {
					int shortV = shortp[x];
	 		        System.out.print(g.citylist[shortV]);
	 		        if(x==0)
	 		        {
						result[flag] = new String(g.citylist[shortV]+"  ");
					}
					else
					{
						result[flag] = new String("经过"+g.citylist[shortV]+" ");
					}
						flag++;
	 		        for (int i = 0 ;i <= g.cityEdge[shortV][shortp[x+1]].autoNum ;i++)
	 		        {
						System.out.print("乘"+g.cityEdge[shortV][shortp[x+1]].autoName[i]);
						result[flag] = new String("乘"+g.cityEdge[shortV][shortp[x+1]].autoName[i]+"次列车 ");
						flag++;
						if(i != g.cityEdge[shortV][shortp[x+1]].autoNum)
						{
							result[flag] = new String("或乘");
							flag++;
						}
	 		        	//result[flag] = new String("到达");
					}
				}
				//打出终点
				System.out.print("到达");
			 	System.out.println(g.citylist[stop]);
			 	result[flag] = new String("到达"+g.citylist[stop]+"\n");
			 	flag++;
	            return;
	 		  }

	 		   for (int i = 0; i < nVerts; i++){
			  		if (shorestMat[v][stop][i] != -1)
			  		{
			  		  	 v = shorestMat[v][stop][i];
			  		  	 shortp[shortnumber++] = v;//赋给最短的一个数组

			  			  if (!visited[v])
			  			  {
			  			  	  search(v,stop,g);
			  			  	  shortnumber--;//编号完成后复位
			  		       }
			  		}
				}
	 		}

	 	public String[] getResult()
	 	{
			return result;
		}
		public static void main(String[] args)
		{
			leastChange least = new leastChange();
				  Graph g = new Graph();
				  cityFile file = new cityFile();
				  file.inputfromInfoFile(g);
				   least.setNum(g.cityNum);
				   least.setShorestMat(g.shorestMat);
			     	least.path(1,3,g);             // shortest paths
			    //  System.out.println(g.adjMat[1][3]);

			    // System.out.print(g.cityNum);
			 		System.out.println();
      		file.outputtoInfoFile(g.records);
  		}
// -------------------------------------------------------------
   }  // end class Graph
////////////////////////////////////////////////////////////////
/*class path
   {
   public static void main(String[] args)
      {
      leastChange least = new leastChange();
	  Graph g = new Graph();
	  cityFile file = new cityFile();
	  file.inputfromInfoFile(g);
	   least.setNum(g.cityNum);
	   least.setShorestMat(g.shorestMat);
     	least.path(1,3,g);             // shortest paths
    //  System.out.println(g.adjMat[1][3]);

    // System.out.print(g.cityNum);
 		System.out.println();
      file.outputtoInfoFile(g.records);
      }  // end main()
   } */ // end class PathApp
////////////////////////////////////////////////////////////////