实验四分支限界法实现单源最短路径

《实验四分支限界法实现单源最短路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验四分支限界法实现单源最短路径09电信实验班109660118徐振飞一、实验名称实现书本P194页所描述的单源最短路径问题二、实验目的(1)掌握并运用分支限界法基本思想(2)运用分支限界法实现单源最短路径问题(3)区分分支限界算法与回溯算法的区别，加深对分支限界法理解三、实验内容和原理(1)实验原理解单源最短路径问题的优先队列式分支限界法用一极小堆(本次实验我采用java.util包中的优先队列类PriorityQueue来实现)来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点S和空优先队列开始。结点S被扩展后，它的儿子结点被依次

2、插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。d1（2）实验内容四、源程序importjava.util.*;publicclassShortestPath{privateintn;privatedoublematrix[][]=null;privatedoubleminpath[

3、];publicShortestPath(intn){this.n=n;matrix=newdouble[n+1][n+1];minpath=newdouble[n+1];for(inti=l;i<=n;i++)minpath[i]=Double.MAX_VALUE;}//初始化图getGraphMatrix();}publicvoidgetGraphMatrix(){//初始化为不能连通for(inti=l;i<=n;i++){for(intj=l;j<=n;j++){matrix[i][j]=Double.MAX_VALUE;}}System,o

4、ut.printIn("请输入边总数：");Scannerscan=newScanner(System.in);intm=scan.nextInt();System,out.println("依次输入两个顶点号(l~"+n+")和边长：例如123”)；for(inti=0;i

5、

6、bn

7、

8、

9、b>n){System,out•printIn(”顶点号不能大于”+n);continue;}matrix[a][b]=d;}}/***@param求以祐i个节点力起点的舉源最短路径*/publicvoidshortpath(inti){minpath[i]=0;doublecurlen=0;PriorityQueueheap=newPriorityQueue();Nodecur=newNode(iz0);heap.add(cur);while(!heap.isEmpty()){for(intj=l;j<=n;j++){if(matr

10、ix[cur.i][j]〈Double.MAX_VALUEcur.len+matrix[cur.i][j]

11、：”+minpath[j]);publicstaticvoidmain(Stringargs[]){System,out.printIn("请输入定点总数：");Scannerscan=newScanner(System.in);intn=scan.nextInt();ShortestPaths=newShortestPath(n);s.shortpath(1);}}classNodeimplementsComparable{inti;doublelen;publicNode(inti,double1){this.i=i;len=1;}p

12、ublicintcompareTo(Nodeo){doubledif=len-o.len;if(dif>0)