贪新算法和分支限界法解单源最短路径.docxVIP

单源最短路径问题问题描述与分析分支限界法解单源最短路径：分支限界法类似于回溯法，是在问题的解空间树上有哪些信誉好的足球投注网站问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。常见的两种分支限界法：队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。单源最短路径问题适合于用分支限界法求解。解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 贪新算法解单源最短路径：Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。算法设计分支限界法：Public class BBShortest{Static classHeapNode implements Comparable{Int I; Float length;HeapNode(int ii, float ll){ I=ii; Length=ll;}Public intcomparator(Object x){ Float xl=((HeapNode)x).length;If(lengthxl)return-1;I if (length==xl) return0;Return 1; }}Staticfloat[][]a;Public static void shortest(intv,float []dist,int []p){Int n=p.length-1;MinHeap heap=new MinHeap();//定义源为初始扩展节点HeapNodeenode=new HeapNode(v,0);for(int j=1;j=n;j++)dist[j]=Float.MAX_VALUE;dist[v]=0;while (true) { // 有哪些信誉好的足球投注网站问题的解空间for (int j=1;j=n;j++)if(a[enode.i][j] Float.MAX_VALUE enode.length+a[enode.i][j] dist[j]) {// 顶点i到顶点j可达，且满足控制约束dist[j]=enode.length+a[enode.i][j];p[j]=enode.i;HeapNode node = new HeapNode(j,dist[j]);heap.put(node); // 加入活结点优先队列 }if (heap.isEmpty()) break;elseenode = (HeapNode) heap.removeMin(); }}}贪新算法：public static void dijkstra(int v){ int n=dist.length-1;if(v1||vn) return; boolean[]s=new boolean[n+1]; for(inti=1;i=n;i++) { dist[i]=a[v][i]; s[i]=false; if(dist[i]0) prev[i]=0; elseprev[i]=v; } dist[v]=0; s[v]=true; for(inti=1;in;i++) { int temp=Integer.MAX_VALUE; int u=v; for(int j=1;j=n;j++) if((!s[j])(dist[j]temp)(dist[j]0)) { u=j; temp=dist[j]; } s[u]=true; for(int j=1;j=n;j++) { if((!s[j])(a[u][j]0)) { intnewdist=dist[u]+a[u][j]; if(newdistdist[j]||dist[j]==-1) { dist[j]=newdist;