fac6_2.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 198 页，例
//单源最短路径问题的分支限界解法
  
  class MinHeap 
   {                          //Min-heap impmentation
     static HeapNode[] Heap;  //Pointer to the heap array
     static int size;         //Maximum size of the heap
     static int n;            //Number of intents now in heapheapsoet
    public MinHeap(HeapNode[] h,int num,int max)//constructor
     { Heap=h;n=num;size=max;buildheap();}
    public int heapsize()//return current size of the heap
     {  return n;}
    public static boolean isLeaf(int pos)//true if pos is a leaf position
     { return(pos>=n/2)&&(pos<n);} 
    public static void Assert_notFalse(boolean p,String q)
     {if(!p)System.out.println((String)q);}
    public static float key( HeapNode [] q,int p)
     {  return q[p].length;}
  //return position for left child of pos
    public static int leftchild(int pos)
     { Assert_notFalse(pos<n/2,"position has no left child");
       return 2*pos+1;
     }
  //return position for right child of pos
    public static int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
     return 2*pos+2;
     }
    public static int parent(int pos)//return position for parent
     {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
     }
    public static  void buildheap() //Heapify contents of Heap
     {  for(int i=n/2-1;i>=0;i--)siftdown(i);}

    public static void swap(HeapNode[] q,int i,int j)
     {      
       HeapNode temp;
       temp=q[i];q[i]=q[j];q[j]=temp;}

    private static void siftdown(int pos) //put intent in itscorrent place
     {Assert_notFalse((pos>=0) && (pos<n),"illegal heap position ");
     while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if((j<(n-1))&&(key(Heap,j)>key(Heap,j+1)))
         j++;// j is now index of child with greater value
       if(key(Heap,pos)<=key(Heap,j)) return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
     }
    public static void insert(HeapNode val) //Insert value into heap
     {
     Assert_notFalse(n<size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;      //start t end of heap
     //Now sift up until curr's parent's key<curr's key
     while((curr!=0)&&(key(Heap,curr)<key(Heap,parent(curr))))
       {
         swap(Heap,curr,parent(curr));
         curr=parent(curr);
       }
      }
    public static HeapNode removeMin()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum with last value
       if(n!=0)     //Not on last intent
       siftdown(0); //Put new heap root val in corrent place 
       return Heap[n];
     }
  //Remove intent at specified position 
    public static HeapNode remove(int pos)
     {
      Assert_notFalse((pos>0)&&(pos<n),"illegal heap position ");
      swap(Heap,pos,--n);//swap with last value
      if(n!=0)     //Not on last intent
      siftdown(pos);//put new heap root val in corrent place
      return Heap[n];
     }
   public static void outMinHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i]+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最小堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removeMin()+"  ");
     System.out.println( );    //removeMin places min value at end of heap
    } 
 }// class MinHeap 

    class HeapNode implements Comparable
    {
       int i;       // 顶点编号
       float length; // 当前路长
     
      HeapNode(int ii,float ll)
       {
         i=ii;
         length=ll;
       }

      public int compareTo(Object x)
       {
        float xl=((HeapNode) x).length;
        if(length<xl) return -1;
        if(length==xl) return 0;
        return 1;
       }
    } 
  class BBSorttest
    {
     static float[][] a;  //图G的邻接矩阵
  
     public static void sorttest(int v,float[] dist,int [] p)
       {
        int n=p.length-1;
        HeapNode []h1=new HeapNode[n];
        MinHeap heap=new MinHeap(h1,0,n);        //定义源为初始扩展结点
        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.n==0)break;
        else enode=(HeapNode)heap.removeMin();
         }
      }
   }



 public class Fac6_2{

      public static void main(String args[])
  {
       BBSorttest abc=new BBSorttest();
       int v1=1;
       final float ff=Float.MAX_VALUE;
       float [][]a1={{0.0f,0.0f,0.0f,0.0f,0.0f,0.0f},
                     {0.0f,0.0f, 10f,  ff, 30f,100f},
                     {0.0f,0.0f,0.0f, 50f,  ff,  ff},
                     {0.0f,  ff,  ff,0.0f,  ff, 10f},
                     {0.0f,  ff,  ff, 20f,0.0f, 60f},
                     {0.0f,  ff,  ff,  ff,  ff,0.0f}};
       int n1=a1[1].length;
       float []d1=new float[n1];
       abc.a=a1;
       int []p1=new int[n1];
      abc.sorttest(v1,d1,p1);
       System.out.println("输出顶点前置点顺序结果  ");
       for(int i=1;i<n1;i++)
       System.out.println("prev["+i+"]="+p1[i]+" dist["+i+"]="+d1[i]);
   
   }    
}