实验三 动态规划法求多段图问题

1、本科实验报告课程名称：算法设计与分析实验项目：动态规划法求多段图问题实验地点：专业班级：学号：学生姓名：指导教师：实验三动态规划法求多段图问题一、实验目的掌握动态规划算法的基本思想掌握多段图的动态规划算法选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。二、实验内容设G=（V,E是一个带权有向图,其顶点的集合V被划分成k2个不相交的子集Vi,lviv=k,其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。求一条s到t的最短路线。参考讲义p136图5-24中的多段图,试选择使用向前递推算法或向后递推算法求解多段图问题。三、

2、实验环境程序设计语言：C+编程工具：microsoftvisualstudio2010四、算法描述和程序代码#include#include#include#include#defineMAX100#definen12#definek5intcnn;voidinit(intcost)/初始化图inti,j;for(i=0;i13;i+)for(j=0;j13;j+)cij=MAX;c12=9;c13=7;c14=3;c15=2;c26=4;c27=2;c28=1;c36=2;c37=7;c48=11;c57=11;c58=8;c69=6;c610=5;c79=4;c710=3;c810=5;c

3、811=6;c912=4;c1012=2;c1112=5;voidfgraph(intcost,intpath,intd)/使用向前递推算法求多段图的最短路径intr,j,temp,min;for(j=0;j=1;j-)temp=0;min=cjtemp+costtemp;/初始化最小值for(r=0;r=n;r+)if(cjr!=MAX)if(cjr+costr)min)/找到最小的rmin=cjr+costr;temp=r;costj=cjtemp+costtemp;dj=temp;path1=1;pathk=n;for(j=2;jk;j+)pathj=dpathj-1;voidbgrap

4、h(intbcost,intpath1,intd)/使用向后递推算法求多段图的最短路径intr,j,temp,min;for(j=0;j=n;j+)bcostj=0;for(j=2;j=n;j+)temp=12;min=ctempj+bcosttemp;/初始化最小值for(r=0;r=n;r+)if(crj!=MAX)if(crj+bcostr)=2;i-)path1i=dpath1i+1;voidmain()intcur=-1;intcost13,d12,bcost13;intpathk;intpath1k;coutttt动态规划解多段图问题endl;coutnn;init(cost);f

5、graph(cost,path,d);coutvv输出使用向前递推算法后的最短路径:nn;for(inti=1;iv=5;i+)coutvvpathivv;coutvvn;coutvvendlvv最短路径为长度:vvcost1vvendl;coutvvn;coutvvn输出使用向后递推算法后的最短路径:nn;bgraph(bcost,path1,d);for(i=1;iv=5;i+)coutvvpath1ivv;coutvvn;coutvvendlvv最短路径为长度:vvbcost12vvendl;coutvvn;五、实验结果截E:法实验D旳期拿卷圏电-动态规划解多段图间题输出使用向前谨推算法石的最短路