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

《实验三动态规划求多段图问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验项仃算法实验动态规划实验一、实验目的1.掌握动态规划算法的基本思想2.掌握多段图的动态规划算法3.选择邻接表或邻接矩阵方式来存储图4.分析算法求解的复杂度。二、实验内容4.掌握动态规划算法的基本思想5.掌握多段图的动态规划算法6.选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。三、实验环境程序设计语言：C++编程丁具：microsoftvisualstudio2010四、算法描述和程序代码#include"stdio.h"#definen7〃图的顶点数#definek4//图的段数#defineMAX2376

2、7intcost[n][n];//成本值数组intpath[k];//存储最短路径的数组voidcreatgraph()//创建图的(成本)邻接矩阵{inti,j;for(i二0;i〈n;i++)for(j=0;j

3、ntf("");//使用向前递推算法求多段图的最短路径voidFrontPath(){inti,j,length,temp,v[n],d[n];for(i=0;i=0;i―){for(length二MAX,j二i+1;j<=n-l;j++)if(cost[i][j]>0&&(cost[i][j])+v[j]<1ength){length二cost[i][j]+v[j];temp=j;}v[i]=length;d[i]=temp;}path[0]=0;//起点path[

4、k-l]=n-l;//最后的目标for(i=l;i<=k-2;i++)(path[i])=d[path[i-l]];//将最短路径存入数组中}voidprintpathO{inti;for(i=0;i

5、n〃)；return0;五、实验结果截图005000;190000000001000190:05400^70000^-20000『，宀3000岀使用向前递推算法所得的最短路径:)246I-俞岀使用向后递推算法所得的最短路径:)246anykeytocontinue六、实验总结在做实验的过程中，要按部就班，首先明确实验目的，然后进行分析，写算法程序，最后调试运行，不能粗枝大叶，做的过程要细心谨慎，自己不会的通过向别人请教，总之上机实践的过程会学到很多。