分支限界法-单源最短路径

学号： 姓名：上机06分支限界法一、问题21、问题描述二、单源最短路径问题给定一个带权图V中的一个顶点，成为源。现在要计算从源到其他所有顶点的最短路径长度（边的权重之和。请使用优先队列式分支限界法，求解该问题。2、算法设计思想分支限界法算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入i到顶点j有边可达，且从源出发，途经ij入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。解向量：X[x1,x2…xn]x1=[1,2…n]表示顶点到第1个…第n个的距离解空间：剪去没有通路的节点后的排列树剪枝函数：在拓展节点的过程中，如果发现加入这个节点产生的距离的下界大于当前找到的最短路径，则减去以这个节点为根节点的子树3、算法过程描述以课本的图为例2,3,42作为第一个拓展节点，将5,4,9排序并放入队列，按照队列的先进先出，把第二行的3并剪去不符合剪枝函数的子树，队列为空时就得到了问题的解4、算法实现及运行结果packagedemoo;importjava.util.Collections;importjava.util.LinkedList;importjava.util.Scanner;publicclassBBShortest{publicstaticclassHeapnodeimplementsComparable{intid;//顶点编号floatlength;//当前路长publicHeapnode(intii,floatll){id=ii;length=ll;}@OverridepublicintcompareTo(Objectx){floatxl=((Heapnode)x).length;if(length<xl)return-1;if(length==xl)return0;return1;}}publicstaticvoidshortest(float[][]a,intv,float[]dist,int[]p){//dist[j]保存从源到顶点j的距离;p[j]记录从源到顶点j的路径上的上一顶点intn=p.length-1;LinkedList<Heapnode>nodes=newLinkedList存储最小堆Heapnodeenode=newHeapnode(v,0);for(intj=1;j<=n;j++){dist[j]=Float.MAX_VALUE;}while(true){//搜索问题解空间for(intj=1;j<=n;j++){if(a[enode.id][j]!=-1&&enode.length+a[enode.id][j]<dist[j]){//ijdist[j]dist[j]=enode.length+a[enode.id][j];p[j]=enode.id;Heapnodee=newHeapnode(j,dist[j]);nodes.add(e);Collections.sort(nodes);}}//取下一个扩展结点if(nodes.isEmpty())break;else{enode=(Heapnode)nodes.poll();}}for(inti=2;i<=n;i++){System.out.println(i+"节点的最短距离是："+dist[i]+"；上一个点是："+p[i]);}}publicstaticvoidmain(String[]args){System.out.println("请输入图顶点的个数：");Scannersc=newScanner(System.in);Stringline=sc.nextLine();intn=Integer.parseInt(line);System.out.println("请输入图的路径长度：");float[][]a=newfloat[n+1][n+1];//下标从1开始，以下都是float[]dist=newfloat[n+1];int[]prev=newint[n+1];for(inti=0;i<n;i++){line= sc.nextLine();String[]ds=line.split(",");for(intj=0;j<ds.length;j++){a[i+1][j+1]=Float.parseFloat(ds[j]);}}intv=1;//顶点从1开始s