bbshortest.java

一个不错的源码

/**
 * @(#)BBShortest.java
 *
 *
 * @author wangwei
 * @version 1.00 2007/12/19
 */

public class BBShortest {
    
    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, 10  , Float.MAX_VALUE, 30  , 100},
       	{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, Float.MAX_VALUE, Float.MAX_VALUE, 10},
       	{Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, 20, Float.MAX_VALUE, 60},
       	{Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE, Float.MAX_VALUE}  	       	
   		};
    public static int[] display = new int[6];
    public  static float[] dist = new float[6];
    public static int[] p = new int[6];
   /**
    * @param a //图G的邻接矩阵
    * @param display 用来打印运算结果
    * @param dist 存入v(i,j)和最短路径
    * @param p 记录最短路径的有顶点信息
    */
    public static void main (String[] args) {

  	   	  BBShortest shortest = new BBShortest();
  	   	  shortest.shortest(1,dist,p);
  	   	  shortest.display(5);
  	   	  
    }

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