《实验三动态规划求多段图问题.docx》由会员分享，可在线阅读，更多相关《实验三动态规划求多段图问题.docx（10页珍藏版）》请在三一文库上搜索。
1、实验项目 算法实验动态规划实验一、实验目的1.2.3.掌握动态规划算法的基本思想掌握多段图的动态规划算法选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。二、实验内容4.5.6.掌握动态规划算法的基本思想掌握多段图的动态规划算法选择邻接表或邻接矩阵方式来存储图4、分析算法求解的复杂度。三、实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、算法描述和程序代码#include #define n 7 / 图的顶点数#define k 4 / 图的段数#define MAX 23767int costnn; / 成本值数组int pathk; /
2、存储最短路径的数组void creatgraph() / 创建图的(成本)邻接矩阵 int i,j;for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&costij);/获取成本矩阵数据void printgraph() / 输出图的成本矩阵 int i,j;printf(成本矩阵:n);for(i=0;in;i+) for(j=0;jn;j+)printf(%d ,costij);printf(n);/使用向前递推算法求多段图的最短路径void FrontPath() int i,j,length,temp,vn,dn;for(i=0;i=0;i-) for(leng
3、th=MAX,j=i+1;j0 & (costij)+vjlength)length=costij+vj; temp=j;vi=length;di=temp;path0=0;/起点pathk-1=n-1;/最后的目标for(i=1;i=k-2;i+) (pathi)=dpathi-1;/ 将最短路径存 入数组中void printpath() int i;for(i=0;ik;i+)printf(%d ,pathi);int main()creatgraph();printgraph();FrontPath();printf(输出使用向前递推算法所得的最短路径 :n);printpath();printf(n 输出使用向后递推算法所得的最短路径:n);printpath();printf(n);return 0;五、实验结果截图六、实验总结在做实验的过程中，要按部就班，首先明确实验目的，然后进行分析，写算法程序，最后调试运行，不能粗枝大叶，做的过程要细心谨慎，自己不 会的通过向别人请教，总之上机实践的过程会学到很多。