数字码影的头像 ID: 96259731533

数字码影

HelloWorld 社区成员

7471979113

文章2
个人网站0
加入社区2025

有向无环图的最长简单路径

给定一个有向无环图$G(V,E)$,边权重为实数,给定图中的两个顶点$k,t$,设计动态规划算法,求从k到t的最长简单路径,子问题图是怎样的?算法的效率如何?算法分析:该问题不能够用贪心求解,假设从k出发,每一步取得weight最大的边,按这样的路径,并不能够保证能走到终点t。所以考虑动态规划