分支限界法求解单源最短路径

有很长时间没有上传了，主要是因为这些天出了些小事。这个是用分支限界法求解单源最短路径问题的算法。

/**
 * @（#）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（ij）和最短路径
    * @param p 记录最短路径的有顶点信息
    */
    public static void main （String[] args） {

  	   	  BBShortest shortest = new BBShortest（）;
  	   	  shortest.shortest（1distp）;
  	   	  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 vfloat[] distint[] p）{
    	int n = p.length - 1;
    	MinHeap heap = new MinHeap（）;
    	//定义源为初始扩展结点
    	HeapNode enode = new HeapNode（v0）;
    	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（jdist[j]）;
    					//向最小堆中插入活结点优先队列
    					heap.insert（node）;
    				}
    				if（heap.isEmpty（））
    					break;
    				else enode = （HeapNode）heap.removeMin（）;
    	}
    }
    
    
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        409  2007-12-20 17:28  HeapNode.java

     文件       2609  2007-12-20 17:28  MinHeap.java

     文件       2794  2007-12-20 17:47  BBShortest.java

----------- ---------  ---------- -----  ----

                 5812                    3