分支限界法-單源最短路徑

學(xué)號(hào)： 姓名：上機(jī)06分支限界法一、問(wèn)題21、問(wèn)題描述二、單源最短路徑問(wèn)題給定一個(gè)帶權(quán)圖V中的一個(gè)頂點(diǎn)，成為源?，F(xiàn)在要計(jì)算從源到其他所有頂點(diǎn)的最短路徑長(zhǎng)度（邊的權(quán)重之和。請(qǐng)使用優(yōu)先隊(duì)列式分支限界法，求解該問(wèn)題。2、算法設(shè)計(jì)思想分支限界法算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開(kāi)始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)ij入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過(guò)程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。解向量：X[x1,x2…xn]x1=[1,2…n]表示頂點(diǎn)到第1個(gè)…第n個(gè)的距離解空間：剪去沒(méi)有通路的節(jié)點(diǎn)后的排列樹(shù)剪枝函數(shù)：在拓展節(jié)點(diǎn)的過(guò)程中，如果發(fā)現(xiàn)加入這個(gè)節(jié)點(diǎn)產(chǎn)生的距離的下界大于當(dāng)前找到的最短路徑，則減去以這個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)3、算法過(guò)程描述以課本的圖為例2,3,42作為第一個(gè)拓展節(jié)點(diǎn)，將5,4,9排序并放入隊(duì)列，按照隊(duì)列的先進(jìn)先出，把第二行的3并剪去不符合剪枝函數(shù)的子樹(shù)，隊(duì)列為空時(shí)就得到了問(wèn)題的解4、算法實(shí)現(xiàn)及運(yùn)行結(jié)果packagedemoo;importjava.util.Collections;importjava.util.LinkedList;importjava.util.Scanner;publicclassBBShortest{publicstaticclassHeapnodeimplementsComparable{intid;//頂點(diǎn)編號(hào)floatlength;//當(dāng)前路長(zhǎng)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]保存從源到頂點(diǎn)j的距離;p[j]記錄從源到頂點(diǎn)j的路徑上的上一頂點(diǎn)intn=p.length-1;LinkedList<Heapnode>nodes=newLinkedList存儲(chǔ)最小堆Heapnodeenode=newHeapnode(v,0);for(intj=1;j<=n;j++){dist[j]=Float.MAX_VALUE;}while(true){//搜索問(wèn)題解空間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);}}//取下一個(gè)擴(kuò)展結(jié)點(diǎn)if(nodes.isEmpty())break;else{enode=(Heapnode)nodes.poll();}}for(inti=2;i<=n;i++){System.out.println(i+"節(jié)點(diǎn)的最短距離是："+dist[i]+"；上一個(gè)點(diǎn)是："+p[i]);}}publicstaticvoidmain(String[]args){System.out.println("請(qǐng)輸入圖頂點(diǎn)的個(gè)數(shù)：");Scannersc=newScanner(System.in);Stringline=sc.nextLine();intn=Integer.parseInt(line);System.out.println("請(qǐng)輸入圖的路徑長(zhǎng)度：");float[][]a=newfloat[n+1][n+1];//下標(biāo)從1開(kāi)始，以下都是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;//頂點(diǎn)從1開(kāi)始s