shortestpath.java

java编写的最短路径算法

package engine;
public class shortestPath {
	public static final int MAXCELLS = 40;
	/** Array of current cell x co-ordinates */
	public int xCell[] = new int[MAXCELLS];
	/** Array of current cell y co-ordinates */
	public int yCell[] = new int[MAXCELLS];
	/** Array of current route */
	public int route[] = new int[MAXCELLS + 1];
	/** current cells number */
	public int cells; 
	
	public double[][] d = new double[MAXCELLS][MAXCELLS]; // distances matrix
	private boolean[] visitedCells = new boolean[MAXCELLS]; // cell is visited or not 
//	public int nr;
	public void preEvaluate(){
		cells = 7;
		xCell[0]=1;
		xCell[1]=1;
		xCell[2]=2;
		xCell[3]=1;
		xCell[4]=2;
		xCell[5]=1;
		xCell[6]=2;
		
		yCell[0]=0;
		yCell[1]=2;
		yCell[2]=2;
		yCell[3]=4;
		yCell[4]=4;
		yCell[5]=6;
		yCell[6]=6;
		
	}
	
	/** Generates random test data. Generates random cells number and random cells co-ordinates. */
	public void randomTestData() {
		
/*		cells = (int) (3 + Math.random() * 5);
		xCell[0]=1;
		yCell[0]=0;
		for (int i = 1; i < cells; i++) {
			xCell[i] = (int) (Math.random() * 4+1);
			yCell[i] = (int) (Math.random() * 7+1);
		}
*/		System.out.print("cells="+cells+"\n");
	}

	
	/** Calculates the traveling sales person distance using Repeatetive Nearest Neighbour calculation method
	 * @return Returns TSP distance.
	 */
	public double repeatetiveNearestNeighbour() {

		double min_dist = Double.MAX_VALUE;
		
		initDistances();
		int i=0;
			
		// clear visited cities values
		for (int k = 0; k < cells; k++){
			visitedCells[k] = false;
			}
		
		// get the distance and route starting from the city i	
		min_dist = nearest_n(i);

		return min_dist;
	}
	
	// nearest neighbour method      
	private double nearest_n(int start) {

		int next_c = 0;
		int i;
		int n;
		i = start;
		double mindist, distance = 0;
		for (n = 0; n < cells; n++) {
			mindist = Double.MAX_VALUE; // let it be, primary minimal distance
			for (int j = 0; j < cells; j++) {
//				iterations++;
				if (n != cells-1) { // to the start cell we return in the last step
					if ((mindist > d[i][j]) && (i != j) && (visitedCells[j] != true) && (j != start)) {
						mindist = d[i][j];
						next_c = j;
					}// find the shortest distance among unvisted cells
				} else {
					mindist = d[i][start];
					next_c = start;
				}
			}

			visitedCells[i] = true;
			distance = distance + mindist;
			route[n] = i; // add visited cell to a route array
			i = next_c; // city to which we go
		}
	
		// return to the start city
		visitedCells[i] = true;
		route[n++] = i;
		return distance;
	}

	// init the matrix of distances values      
	private void initDistances() {
//		Initializing distance matrix for best route calculation
			for (int i = 0; i < cells; i++) {
				for (int j = 0; j < cells; j++) {
					if (i == j) {
						d[i][j] = 0;
					} else {
						d[i][j] = (Math.sqrt((double) ((xCell[i] - xCell[j])
										* (xCell[i] - xCell[j])*705*705 + (yCell[i] - yCell[j])
										* (yCell[i] - yCell[j])*385*385)));
					}
				}
				visitedCells[i] = false; // at the begining all cities are not visited
//				iterations = 0; // at the beginning number of iterationss is zero
			}
			for(int i=0;i<cells;i++){
				for(int j=0;j<cells;j++){
				System.out.print("d["+i+"]["+j+"]="+d[i][j]+"\n");}
		}}

}