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

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

2、算法或向后递推算法求解多段图问题。三、 实验环境程序设计语言：c+编程工具：microsoft visual studio 2010四、 算法描述和程序代码#include #include #include #include #define MAX 100 #define n 12 #define k 5 int cnn; void init(int cost) /初始化图 int i,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=

3、7; c48=11; c57=11; c58=8; c69=6; c610=5; c79=4; c710=3; c810=5; c811=6; c912=4; c1012=2;c1112=5; void fgraph(int cost,int path,int d) /使用向前递推算法求多段图的最短路径 int r,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) /找到最小的r min=cjr+costr; temp=r

4、; costj=cjtemp+costtemp; dj=temp; path1=1; pathk=n; for(j=2;jk;j+) pathj=dpathj-1; void bgraph(int bcost,int path1,int d)/使用向后递推算法求多段图的最短路径 int r,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; void main() int cur=-1; int cost13,d12,bcost13; int pathk; int path1k; coutttt动态规划解多段图问题endl; coutnn; init(cost); fgraph(cost,path,d); cout输出使用向前递推算法后的最短路径:nn; for(int i=1;i=5;i+) coutpathi ; coutn; coutendl最短路径为长度:cost1endl; coutn; coutn输出使用向后递推算法后的最短路径:nn; bgraph(bcost,path1,d); for(i=1;i=