求帮算法作业！用动态规划法求解最长路径问题实验目标： （1）掌握用动态规划方法求解实际问题的基本思路。 （2）进一步理解动态规划方法的实质，巩固设计动态规划算法的基本步骤。 实验任务： 设计动态规划算法求解最长路径问题（见下面附录部分），要求程序能根据给定的图作为输入，输出最长路径的长度及一条最长的路径。 实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： 根据实验目标，明确实验的具体任务； 分析问题获得递推计算的公式； 设计求解问题的动态规划算法，并编写
2019-06-27
求帮算法作业！用动态规划法求解最长路径问题实验目标： （1）掌握用动态规划方法求解实际问题的基本思路。 （2）进一步理解动态规划方法的实质，巩固设计动态规划算法的基本步骤。 实验任务： 设计动态规划算法求解最长路径问题（见下面附录部分），要求程序能根据给定的图作为输入，输出最长路径的长度及一条最长的路径。 实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： 根据实验目标，明确实验的具体任务； 分析问题获得递推计算的公式； 设计求解问题的动态规划算法，并编写程序实现算法； 使用数据测试程序； 分析算法的时间和空间复杂度，并由此解释释相应的实验结果； [附] 最长路径问题（见教材第143页习题7.34） 已知G= 是一个有n个顶点的有向无回路的带权图（边权都为正整数）。设s和t是V中的两个顶点，其中s的入度为0，t的出度为0。请设计一个动态规划算法求G中从s到t的最长路径的长度及一条最长的路径，并分析该算法的时间复杂度。
优质解答
先对图进行拓扑排序 一个结果为s b a c d t 拓扑排序的时候初始化dist[i] 表示从s到i的距离 dist[i]=max{dist[u]+edge[u][i], dist[i]}. i从s取到t 最终得结果
先对图进行拓扑排序 一个结果为s b a c d t 拓扑排序的时候初始化dist[i] 表示从s到i的距离 dist[i]=max{dist[u]+edge[u][i], dist[i]}. i从s取到t 最终得结果