distancevector.java

实现简单的模拟路由算法,使学习者通过程序,对该算法有更深更新的了解

import java.io.*;
public class DistanceVector
{
   int d1[][] = new int[5][5];
   int d2[][] = new int[5][5];
   int d3[][] = new int[5][5];
   int d4[][] = new int[5][5];
   int dmin1[] = new int[5];
   int dmin2[] = new int[5];
   int dmin3[] = new int[5];
   int dmin4[] = new int[5];
   int c[][]={{0,0,0,0,0},{0,0,1,7,3},{0,1,0,99,1},{0,7,99,0,2},{0,3,1,2,0}};
 
   public DistanceVector()
   {
      int start=0,end=0;
      int a,b,t;
      String in;
      init();
      try
      {
       BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
       System.out.println("Please input start point(1-4):");
       in = br.readLine();
       System.out.println("Please input end point(1-4):");
       start = Integer.parseInt(in);
       in = br.readLine();
       end = Integer.parseInt(in);
       if(start==end)
          System.out.println("Total cost is 0.");
       else
          {
             exchange();
             result(start,end,0);
          }
       System.out.println("Do you change value?");
       in=br.readLine();
       if(in.equals("yes"))
          {
           System.out.println("Please input the new value:");
           in=br.readLine();
           a=Integer.parseInt(in);;
           in=br.readLine();
           b=Integer.parseInt(in);;
           in=br.readLine();
           t=Integer.parseInt(in);
           c[a][b]=t;
           c[b][a]=t;
           initnode();
           System.out.println("Please input start point(1-4):");
           in = br.readLine();
           start = Integer.parseInt(in);
           System.out.println("Please input end point(1-4):");
           in = br.readLine();
           end = Integer.parseInt(in);
           if(start==end)
           System.out.println("Total cost is 0.");
           else
             {
              exchange();
              result(start,end,0);
              }
          }
       }
         catch(IOException ioe)
          {}
    }

   public void init()
   {
      int i,j;
      for(i=1;i<=4;i++)
       for(j=1;j<=4;j++)
        {
         d1[i][j]=99;
         d2[i][j]=99;
         d3[i][j]=99;
         d4[i][j]=99;
        }
       initnode();
   }

   public void initnode()
   {
     
      d1[2][2]=c[1][2];
      d1[3][3]=c[1][3];
      d1[4][4]=c[1][4];
      d2[1][1]=c[2][1];
      d2[4][4]=c[2][4];
      d3[1][1]=c[3][1];
      d3[4][4]=c[3][4];
      d4[1][1]=c[4][1];
      d4[2][2]=c[4][2];
      d4[3][3]=c[4][3];
      dmin1[2]=d1[2][2];
      dmin1[3]=d1[3][3];
      dmin1[4]=d1[4][4];
      dmin2[1]=d2[1][1];
      dmin2[3]=99;
      dmin2[4]=d2[4][4];
      dmin3[1]=d3[1][1];
      dmin3[2]=99;
      dmin3[4]=d3[4][4];
      dmin4[1]=d4[1][1];
      dmin4[2]=d4[2][2];
      dmin4[3]=d4[3][3];
   }

   public static void main(String[] args)
   {
      DistanceVector route = new DistanceVector();
   }   

   public void exchange()
    {
      int i,j,flag;
      flag=0;
      for(i=2;i<=4;i++)
         for(j=2;j<=4;j++)
         {
            if(i!=j)
            {
                if(j==2)
                   d1[i][j]=c[1][j]+dmin2[i];
                if(j==3)
                   d1[i][j]=c[1][j]+dmin3[i];
                if(j==4)
                   d1[i][j]=c[1][j]+dmin4[i];
            }    
         }

      for(i=1;i<=3;i++)
         for(j=1;j<=3;j++)
         {
            if(i!=j)
            {
                if(j==1)
                   d4[i][j]=c[4][j]+dmin1[i];
                if(j==2)
                   d4[i][j]=c[4][j]+dmin2[i];
                if(j==3)
                   d4[i][j]=c[4][j]+dmin3[i];
            }
         }

      for(i=1;i<=4;i++) 
         for(j=1;j<=4;j++)
         {
            if(i!=j&&j!=2&&i!=2)
            {
                if(j==1)
                   d2[i][j]=c[2][j]+dmin1[i];
                if(j==3)
                   d2[i][j]=c[2][j]+dmin3[i];
                if(j==4)
                   d2[i][j]=c[2][j]+dmin4[i];
            }
         }

      for(i=1;i<=4;i++) 
         for(j=1;j<=4;j++)
         {
            if(i!=j&&j!=3&&i!=3)
            {
                if(j==1)
                   d3[i][j]=c[3][j]+dmin1[i];
                if(j==2)
                   d3[i][j]=c[3][j]+dmin2[i];
                if(j==4)
                   d3[i][j]=c[3][j]+dmin4[i];
            }
         }

      for(i=2;i<=4;i++)
         for(j=2;j<=4;j++)
         {
             if(d1[i][j]>0)          
             {
                dmin1[i]=d1[i][j];
                flag=1;
             }
         }

      for(i=1;i<=3;i++)
         for(j=1;j<=3;j++)
         {
            if(d4[i][j]>0)           
              {
                dmin4[i]=d4[i][j];
                flag=1;
              }
         }

      for(i=1;i<=4;i++)
         for(j=1;j<=4;j++)
         {
            if(i!=2&&j!=2)
             if(d2[i][j]>0)             
                {
                  dmin2[i]=d2[i][j];  
                  flag=1;
                }
         }

      for(i=1;i<=4;i++)
         for(j=1;j<=4;j++)
         {
            if(i!=3&&j!=3)
                if(d3[i][j]>0)           
               {
                  dmin3[i]=d3[i][j];  
                  flag=1;
                }
         }
      
       }

  public void result(int a,int b,int c)
  {
  int i;
  int min=99;
  int next=0;
  if(a==1)
  {
     for(i=2;i<=4;i++)
     {
      if(d1[b][i]>0)  
       {
        min=d1[b][i];
        next=i;
       }
      }
     if(next!=b)
      {
       if(c==0)
        {
         System.out.println("Total cost is "+min);
         System.out.print("Route is: "+a+"->");
         }
         System.out.print(String.valueOf(next)+"->");
         result(next,b,1);
       }
     else
       {    
        if(c==0)
         {
         System.out.println("Total cost is "+min);
         System.out.print("Route is: "+a+"->");
         }
         System.out.print(String.valueOf(next)+"\n");
        }
  }
  if(a==2)
    {
     for(i=1;i<=4;i++)
         {
            if(i==2)
                continue;
            if(d2[b][i]>0)  
             {
                min=d2[b][i];
                next=i;
             }
         }
    if(next!=b)
        {
         if(c==0)
          {
           System.out.println("total cost is "+min);
           System.out.print("Route is: "+a+"->");
          }
         System.out.print(String.valueOf(next)+"->");
         result(next,b,1);
         }
    else
       {    
        if(c==0)
         {
          System.out.println("total cost is "+min);
          System.out.print("Route is: "+a+"->");
          }
        System.out.print(String.valueOf(next)+"\n");
         }
    }
  if(a==3)
      {
       for(i=1;i<=4;i++)
         {
            if(i==3)
                continue;
            if(d3[b][i]>d3[i][b])          
           {
                min=d3[b][i];
                next=i;
            }
         }
       if(next!=b)
          {
           if(c==0)
           {
            System.out.println("total cost is "+min);
            System.out.print("Route is: "+a+"->");
           }
           System.out.print(String.valueOf(next)+"->");
           result(next,b,1);
          }
       else
         {    
          if(c==0)
          {
           System.out.println("total cost is "+min);
           System.out.print("Route is: "+a+"->");
          }
           System.out.print(String.valueOf(next)+"\n");
        }
      }
   if(a==4)
     {
      for(i=1;i<=3;i++)
       {
          if(d4[b][i]>0) 
          {
             min=d4[b][i];
             next=i;
          }
        }
      if(next!=b)
      {
       if(c==0)
          {
          System.out.println("Total cost is "+min);
          System.out.print("Route is: "+a+"->");
          }
          System.out.print(String.valueOf(next)+"->");
          result(next,b,1);
         }
       else
        {    
       if(c==0)
         {
          System.out.println("total cost is "+min);
          System.out.print("Route is: "+a+"->");
         }
          System.out.print(String.valueOf(next)+"\n");
        }
    }
  }
}