实验三-动态规划法求多段图问题4页.docx

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