《实验四分支限界法实现单源最短路径》由会员分享，可在线阅读，更多相关《实验四分支限界法实现单源最短路径（7页珍藏版）》请在金锄头文库上搜索。
1、实验四 分支限界法实现单源最短路径09 电信实验班 I09660118 徐振飞、实验名称实现书本 P194页所描述的单源最短路径问题、实验目的1）掌握并运用分支限界法基本思想2）运用分支限界法实现单 源 最短路径问题3）区分分支限界算法与回溯算法的区别，加深对分支限界法理解、实验内容和原理1）实验原理 解单源最短路径问题的优先队列式分支限界法用一极小堆 （本次实 验我采用 java.util 包中的优先队列类 PriorityQueue 来实现）来存储 活结点表。其优先级是结点所对应的当前路长。算法从图 G 的源 顶点 s 和空优先队列开始。 结点 s被扩展后，它的儿子结点被依次 插入堆中。此
2、后，算法从堆中取出具有最小当前路长的结点作为当 前扩展结点， 并依次检查与当前扩展结点相邻的所有顶点。 如果从 当前扩展结点 i 到顶点 j 有边可达，且从源出发，途经顶点 i 再到 顶点 j 的所相应的路径的长度小于当前最优路径长度， 则将该顶点 作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继 续到活结点优先队列为空时为止。（2）实验内容测试用例：四、源程序import java.util.*;public class ShortestPath private int n;nullprivatedouble matrix =privatedouble minpath ;publ
3、ic ShortestPath( int n)this . n = n;matrix = new double n+1n+1; minpath = new double n+1;for ( int i=1;i=n;i+)minpath i = Double. MAX_VALUE; / 初始化图 getGraphMatrix();public void getGraphMatrix()/ 初始化为不能连通for ( int i=1;i= n ;i+)for ( int j=1;j= n ;j+)matrix ij = Double.MAX_VALUE ;System. out .println(
4、 请输入边总数： ); Scanner scan =new Scanner(System. in );int m = scan.nextInt();System. out .println( 依次输入两个顶点号 (1 +n+) 和边长 : 例如 1 2 3 );for ( int i=0;im;i+) int a,b; double d;a = scan.nextInt();b = scan.nextInt();d = scan.nextDouble();if (a1 | b n|b n)System. out .println( 顶点号不能大于 +n); continue ;matrix a
5、b = d;* param 求以第 i 个节点为起点的单源最短路径 */public void shortpath( int i) minpath i = 0;double curlen = 0;PriorityQueue heap =Node cur = new Node(i,0); heap.add(cur);new PriorityQueue();while (!heap.isEmpty()for ( int j=1;j=n ;j+)if ( matrix cur. len +matrix cur. i jminpacur. i jDouble. minpath j)MAXVALUE&t
6、h j = cur.len+matrixcur. i j;heap.add(new Node(j,minpathj);cur = heap.poll();/ 打印最短路径结果System. out .println( 最短路径： ); for ( int j=1;j=n ;j+)if ( minpath jDouble. MAX_VALUE & j!=i) System.out .println(i+到+j+ : +minpath j);public static void main(String args )System. out .println( 请输入定点总数： );Scanner s
7、can =new Scanner(System. in );int n = scan.nextInt();ShortestPath s =new ShortestPath(n);s.shortpath(1);class Node implements Comparable int i ;double len ;public Node( int i, double l)this . i = i; len = l;public int compareTo(Node o)double dif =len -o. len ;if (dif0)return 1;else if (dif=0)return 0;elsereturn -1;五、实验结果输出结果分析：测试为上述测试用途，输出结果： 1到 2的最短路径为 3,1到 3 的最短路径为 2,1到4的最短路径为 3,1到 5的最短路径为 7,1到 6的最短路径 为 6 。输出结果正确。六、实验心得和体会通过实验， 了解了分支限界法的基本思想。 知道了分支限界算法与 回 溯 算法的区别 。由 于本 次 实 验利 用 java.util 包下 的 PriorityQueue 代替算法中最小堆，免去了编写实现最小堆的程序 代码（但这并不表示我不会编写最小堆程序，在这次实验中，最 小堆的实现并不是主要部分） ，所以本次实验实现的相对顺利。
