实验五：分枝限界法_最短路径问题.doc

《实验五：分枝限界法_最短路径问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY算法设计与分析实验报告实验项目实验五实验类别验证性学生姓名王龙学生学号201400797完成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。【实验性质】验证性实验。【实验内容与要求】采用分支限界法编程求源点0到终点6的最短路径及其路径长度。要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。【算法思想及处理过程】由于要找的是从源到各顶点的最短路径，所以选用

2、一个数组存起来.Fenzhi函数:由于先前赋值时,用一个二维数组将结点的有向图标记存起来了(有边为1,无边为0),并且又用另外一个二维数组将其权重存起来了;首先,通过双重for循环,通过if语句判断,如果标记为1,并且相加的权重小于先前最优权重(在初始化的时候,对最优权重赋上一个最大值),则求得最优权重,并且用一维数组将权重存起来,而且用一维数组将前驱结点存起来.你然后,一直循环下去,直到循环到目的结点.【程序代码】#include#defineMAX9voidinput(intd[],ints[],intt[][MA

3、X],intti[][MAX],intn,intk);voidfenzhi(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk);voidoutput(intd[],ints[],intn);intmain(){intn,k;intd[MAX],s[MAX],t[MAX][MAX]={0},ti[MAX][MAX]={0};n=7;k=11;printf("请输入结点的个数:");scanf("%d",&n);printf("请输入结点的边数:");scanf("%d",&k);input(

4、d,s,t,ti,n,k);fenzhi(d,s,t,ti,n,k);output(d,s,n);return0;}voidinput(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk){inti,j,m,z;printf("请输入图的边:");for(z=0;z

5、1;}}voidfenzhi(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk){inti,j,zi;d[0]=0;s[0]=-1;for(i=0;it[i][j]+d[i]){d[j]=t[i][j]+d[i];//最短长度s[j]=i;//前驱结点}if(j!=n/*&&j!=6*/)printf("入队结点：%d,最

6、优权重：%d",j,d[j]);}}printf("");}}voidoutput(intd[],ints[],intn){inti,j=0,zi[MAX];printf("从源点到各个结点的最短路径:");for(i=0;i%d",zi[j]);while

7、(zi[j]!=0){j++;zi[j]=s[zi[j-1]];printf("---->%d",zi[j]);}printf("");}【运行结果】图1输入数据图2输出扩展结点图3最终结果【算法分析】本程序的主要函数ShorestPaths的时间复杂度为:O(n*(n-1)),最坏时间复杂度为:O(n*n)【实验总结】