bestway1.java

最短路径算法的一种高效实现。适合在节点密集的环境中找两点之间的最短路径。

/*
 * BestWay1.java
 *
 * Created on 2007年5月12日, 下午2:50
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */


 /*
  * 湖南大学本科毕业设计
  * 最短路径算法改进（一）
  * 作者 陈银
  * 版本 1.0
  * 2007-5-12
  */
import java.math.*;
import java.util.ArrayList;
import java.util.List;
import java.awt.*;
import javax.swing.*;

public class BestWay1 {

 static int maxint = 100;//unreachale
 static int N = 5;
 static int[][] c = new int[N+1][N+1];
 static int path[]={0,0,0,0,0,0};//store paths
 static int s=-1;//start potint
 static int d=-1;//end point
 //static int change=0;//
 
 public static void main(String[] args) {

//initiall the paths
  for(int i = 1;i <= N;i++)
   for(int j = 1; j <= N;j++)
  c[i][j] = maxint;
  c[1][3] = c[3][1]=5;  
  c[1][4] = c[4][1]=6;
  c[3][5] = c[5][3]=5;
  c[3][4] = c[4][3]=1;
  c[4][2] = c[2][4]=7;
  c[4][5] = c[5][4]=6;

//get the start and end points
  String startPoint=JOptionPane.showInputDialog("Enter the start point");
  s=Integer.parseInt(startPoint);	
  String endPoint=JOptionPane.showInputDialog("Enter the end poin");
  d=Integer.parseInt(endPoint);
  if(s>d){
  	BestWay(d,s,c);
  	//change=1;
  	System.out.print("  "+"changged");
  }
  else BestWay(s,d,c); 
  
  }
 

 public static void BestWay(int n,int b,int c[][]){
 	//n is the current node
 	double maxValue;
 	double temp;
 	int k=0;
 	int path[]={0,0,0,0,0,0};
 	int count=1;
 	int x[]={0,0,9,4,4,8};
 	int y[]={0,0,0,3,4,0};
    double u=0;
    double m=0;
    double p=0;
    double q=0;
    path[0]=n;
    
    while(n!=b){
 		
 		maxValue=0;
 		 k=0;
 		for(int i=1;i<=N;i++)
 		{
 		  	if(c[n][i]!=maxint)
 		  	{
 		  		{
 		  		
 		  		  u=(x[i]-x[n])*(x[b]-x[n]);
 		  		  m=(y[i]-y[n])*(y[b]-y[n]);
 		  		  p=(x[i]-x[n])*(x[i]-x[n])+(y[i]-y[n])*(y[i]-y[n]);
 		  		  q=(x[b]-x[n])*(x[b]-x[n])+(y[b]-y[n])*(y[b]-y[n]);
 		  		  temp=(m+u)/(Math.sqrt((double)p)* Math.sqrt((double)q));
 		  		  
 		  		  if(temp>maxValue)
 		  		  {
 		  		  maxValue=temp;
 		  		  k=i;
 		  		  }
 		  		}
 		  	}
 		}
 		n=k;
 		path[count++]=k;
 	}
 
    if(s<d)
    {
      
      for(int j=0;j<=N;j++)
 	  {
 	  	 if(path[j]!=0)System.out.print(path[j]+" ");
 	   }
 	}
 	else for(int h=N;h>=0;h--)
 	{
 		 if(path[h]!=0)System.out.print(path[h]+" ");
 	}
 	
 }
}