Tag: 最长路径

如何在两个节点之间找到循环图中最长的路径？

我已经解决了这里发布的大多数问题，除了最长的路径之外。 我已经阅读了关于最长路径的维基百科文章，如果图形是非循环的，那么这似乎是一个简单的问题，而我的不是。 那我怎么解决这个问题呢？ 蛮力，通过检查所有可能的路径？ 我怎么开始这样做？ 我知道它会在图表上获得很多~18000。 但我只是想开发它，因为它是项目所需要的，我只是测试它并在一个较小比例的图形上向教师显示，执行时间只有一两秒钟。 至少我完成了所有必需的任务，并且我有一个运行的概念certificate它可以工作但是在循环图上没有更好的方法。 但我不知道从哪里开始检查所有这些路径……