实验五分枝限界法最短路径问题

HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY算法设计与剖析实验报告实验项目实验五实验类型考证性学生姓名王龙学生学号7达成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。【实验性质】考证性实验。【实验内容与要求】采纳分支限界法编程求源点0到终点6的最短路径及其路径长度。要求达成：⑴算法描绘⑵写出程序代码⑶达成调试⑷进行过程与结果剖析。【算法思想及办理过程】因为要找的是从源到各极点的最短路径，因此采纳一个数组存起来.Fenzhi函数:因为先前赋值时,用一个二维数组将结点的有向图标志存起来了(有边为1,无边为0),并且又用此外一个二维数组将其权重存起来了;第一,经过两重for循环,经过if语句判断,假如标志为1,并且相加的权重小于先前最优权重(在初始化的时候,对最优权重赋上一个最大值),则求得最优权重,并且用一维数组将权重存起来,并且用一维数组将前驱结点存起来.你而后,一直循环下去,直到循环到目的结点.【程序代码】include<>defineMAX9voidinput(intd[],ints[],intt[][MAX],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(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("请输入图的边:<i,j,t[i][j]>\n");for(z=0;z<k;z++){scanf("%d%d%d",&i,&j,&m);t[i][j]=m;ti[i][j]=1;}for(i=0;i<n;i++)//初始化数组{d[i]=99;//赋个最大值s[i]=-1;}}voidfenzhi(intd[],ints[],intt[][MAX],intti[][MAX],intn,intk){inti,j,zi;d[0]=0;s[0]=-1;for(i=0;i<n;i++){printf("目前扩展节点：%d，权重：%d:\n",i,d[i]);for(j=0;j<n;j++){if(ti[i][j]==1){if(d[j]>t[i][j]+d[i]){d[j]=t[i][j]+d[i];//最短长度s[j]=i;//前驱结点}if(j!=n/*&&j!=6*/)printf("入队结点：%d,最优权重：%d\n",j,d[j]);}}printf("\n");}}voidoutput(intd[],ints[],intn){inti,j=0,zi[MAX];printf("从源点到各个结点的最短路径:\n");for(i=0;i<n;i++)printf("dist[%d]=%d\n",i,d[i]);printf("\n");printf("从源点到终点的最短路径长度为:%d\n",d[n-1]);printf("其路径为:%d",n-1);zi[j]=s[n-1];printf("---->%d",zi[j]);while(zi[j]!=0){j++;zi[j]=s[zi[j-1]];printf("---->%d",zi[j]);}printf("\n");}【运转结