shortpath.java

通过分支限界的方法

/**
a //图的邻接矩阵
    display //用来打印运算结果
    path //存入v(i,j)和最短路径
    v //记录最短路径的顶点信息
    **/
public class Shortpath 
{
    public static int[] display = new int[10];
    public static float[] path = new float[10];
    public static int[] v = new int[10];
	 public static float[][] a={
		{Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE,Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE},
       {Float.MAX_VALUE, Float.MAX_VALUE, 10  , Float.MAX_VALUE, 30  , 100 , Float.MAX_VALUE, 30  , 100 , 110 },
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 50, Float.MAX_VALUE, Float.MAX_VALUE, 50, Float.MAX_VALUE, Float.MAX_VALUE},
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 10, Float.MAX_VALUE, Float.MAX_VALUE, 10,20},
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 30, Float.MAX_VALUE, 60, Float.MAX_VALUE, 30, Float.MAX_VALUE, 60},
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE},  	       	 	{Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE},
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE},
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 50, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 50},
       {Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 10, Float.MAX_VALUE, Float.MAX_VALUE, 10,Float.MAX_VALUE},
       };

        public static void main (String[] args) 
{
  	   	  Shortpath shortest = new Shortpath();
  	   	  shortest.shortest(1,path,v);
  	   	  shortest.display(5);
  	   	  
    }
   
 public Shortpath() {
    }
 	/**
 	 display(int n):显示顶点w到顶点n的最短路径的长度及路径
 	 */
public void display(int n){
 		System.out.println("到顶点" + n + "的最短路径长度是：" + path[n]);
 		System.out.print("最短路径是：");
 		display[1] = v[n];//把目标点的前驱给display[1]
 		int i;
 		for( i = 2;display[i - 1] != 1 && i <= 9;i++)
 			display[i] = v[display[i - 1]];
 		//display[i++] = n;
 		//int i = 2;
 		//do{
 		//	display[i] = prev[display[i - 1]];
 		//	i++;
 		//}
 		//while( != 1);
 		
 		for(int j = 9;j > 0;j--){
 			if(display[j] != 0)
 				System.out.print(display[j] + " ");
 		}
 		System.out.println(n);
 	}
	
    public static void shortest(int w,float[] path,int[] v){
    	int n = v.length - 1;
    	MinHeap heap = new MinHeap();
    	//定义源为初始扩展结点
    	AliveNode enode = new AliveNode(w,0);
    	for(int j = 1;j <= n;j++)
    		path[j] = Float.MAX_VALUE;
    	path[w] = 0;
    	while(true){
    		//搜索问题的解空间
    		for(int j = 1;j <= n;j++)
    			if(a[enode.i][j] < Float.MAX_VALUE &&
    				enode.length + a[enode.i][j] < path[j]){
    					//顶点I到J可达，且满足控制约束
    					path[j] = enode.length + a[enode.i][j];
    					v[j] = enode.i;
    					AliveNode node = new AliveNode(j,path[j]);
    					//向最小堆中插入活结点优先队列
    					heap.insert(node);
    				}
    				if(heap.isEmpty())
    					break;
    				else enode = (AliveNode)heap.removeMin();
    	}
    }