find.java

用分枝界限法找图的最短路径

package graphic;

public class find {
    int nodenum;
    int arcs;
    final int size=5;
    int path[],tempath[];
    int count,sum,min;
    boolean visited[];boolean []flag;
    ArcNode []data;boolean stop=false;

    public find(int nodenum_,ArcNode[] data_) {
        nodenum=nodenum_;count=1;sum=0;min=10000;
        visited= new boolean[nodenum+1];
        path=new int[nodenum+1];
        tempath=new int[size+10];
        data=data_; flag=new boolean[10];
 //     for(int i=0;i<data.length && data[i]!=null;i++)
 //         System.out.print(data[i].getPoint1()+","+data[i].getPoint2()+","+data[i].getValue()+" ");
        for (int i=0;i<nodenum;i++)
        {
            path[i] = 0;
            tempath[i]=0;
            visited[i]=false;
       //     data[i]=new ArcNode();
        }
        tempath[0]=1;
        path[0]=1;
    }

    void search(int begin){
        visited[begin]=true;
        int st=1;
        while(flag[st]==true && st<flag.length)
            st++;
       for(st=1;st<=flag.length+1 && flag[st]==true;st++);
       if (st<flag.length) stop = false;
        else stop = true;

        if(stop==true)
           return;

        if(count==nodenum)
        {
            tempath[count]=1;sum=0;
            for(int i=0;i<count;i++)
                sum+=getValue(tempath[i],tempath[i+1]);

            if(sum<min)
            {
                min=sum;
                for (int i = 0; i <=count && tempath[i]!=0; i++)
                    path[i] = tempath[i];
            }
            for(int i=0;i<=count;i++)
                System.out.print(tempath[i]+",");
            System.out.println("sum:"+sum);
 //           visited[count]=false;
 //           count--;

        }

        else
            {
                for(int i=1;i<=nodenum;i++)
                {
              //      sum+=getValue(tempath[i],tempath[i+1]);
                    if (visited[i] == false )
                    {
                        for (int j = 1; j <= count; j++)
                        {
                            if (count == 1)
                                tempath[j] = i;
                            else {
                                for (int k = count; k > j; k--)
                                    tempath[k] = tempath[k - 1];
                                tempath[j] = i;
                            }
                            count++;

                            search(i);
                            visited[i] = false;

                            for (int s = j; s <= count + 1; s++)
                                tempath[s] = tempath[s + 1];
                            count--;
                        }//inside for
                        flag[i]=true;
                    }//if

        }//outside for

        }
    }

    int getValue(int node1,int node2)
    {
        int value=0;
        for(int i=0;i<data.length && data[i]!=null;i++)
            if((node1==data[i].point1&& node2==data[i].point2)||(node2==data[i].point1&& node1==data[i].point2))
            {
                value=data[i].value;
                break;
            }
        return value;
    }
}