※ 引述《CMturtle (杰尼龟)》之铭言： : 是说~~~一般最短路的演算法为什麽不能处理最长路阿？？ : 我的想法是 : 在无相图中会出现正环的关系 : 但是如果再「有向无环图」（DAG）中 : 是不是就可以套用最短路的算法来写最长路？ : 而bellman-ford & SPFA应该也可以再有向图中来判断正环罗？？ 最短路径演算法(不管哪一个)的核心概念是动态规画 Dynamic Programming 而要能够做 DP 的题目必须要有「最佳子结构」或「重叠子问题」 这代表我可以把一个题目拆成比较「小」的数个类似题 前者是这些小问题的最佳解可以构成我们的最佳解 後者则是这些小问题会一再地重覆计算 这里的小并不一定是数字上的小 也许是数量上的少等等 (和递回的概念几乎相同 只不过计算方向上递回是 top-down 而 DP 是 bottom-up 而已) 最短路径问题上 单源非负最短路径的「小」问题是起始点到稍近一点的点的距离 这是「重叠子问题」 其他的最短路径的「小」问题则是只经过 k 号以前中介点的最短距离 这是「最佳子结构」 但最长路径这个问题并没有如此的性质 我们并不能找到一些「小」的最长路径问题的结果能够拿来构筑原来的最长路径 因此必须另寻他法来解决这个问题 而这些其他方法中也许需要其他演算法来侦测正圈 但解题的演算法主体并不会是它们 -- 実琴：「河野！你真的就这样被物质慾望给吸引过去了吗?!」 亨：「只要穿着女装摆出亲切的样子，所有必要花费就能全免，似乎一点都不坏啊。」 実琴：「难道你没有男人的尊严了吗?!」 亨：(断然道)「没有。在节衣缩食且生活吃紧的学生面前，没有那种东西。」 －－プリンセス・プリンセス 第二话 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.28.92