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

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

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

2、和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。（2）实验内容测试用例：一、源程序importjava.util.*;publicclassShortestPath{private

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

4、for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){matrix[i][j]=Double.MAX_VALUE;}}System.out.println("请输入边总数：");Scannerscan=newScanner(System.in);intm=scan.nextInt();System.out.println("依次输入两个顶点号(1~"+n+")和边长:例如123");for(inti=0;i

5、xtInt();b=scan.nextInt();d=scan.nextDouble();if(a<1

6、

7、b<1){i--;System.out.println("顶点号不能小于1");continue;}if(a>n

8、

9、b>n){i--;System.out.println("顶点号不能大于"+n);continue;}matrix[a][b]=d;}}/***@param求以第i个节点为起点的单源最短路径*/publicvoidshortpath(inti){minpath[i]=0;doubl

10、ecurlen=0;PriorityQueueheap=newPriorityQueue();Nodecur=newNode(i,0);heap.add(cur);while(!heap.isEmpty()){for(intj=1;j<=n;j++){if(matrix[cur.i][j]

11、newNode(j,minpath[j]));}}cur=heap.poll();}//打印最短路径结果System.out.println("最短路径：");for(intj=1;j<=n;j++){if(minpath[j]

12、cannerscan=newScanner(System.in);intn=scan.nextInt();ShortestPaths=newShortestPath(n);s.shortpath(1);}}classNodeimplementsComparable{inti;doublelen;publicNode(inti,doublel){this.i=i;len=l;}publicintcompareTo(Nodeo){doubledif=len-o