※ 引述《CMturtle (杰尼龟)》之铭言： : 是说~~~一般最短路的演算法为什麽不能处理最长路阿？？ : 我的想法是 : 在无相图中会出现正环的关系 : 但是如果再「有向无环图」（DAG）中 : 是不是就可以套用最短路的算法来写最长路？ : 而bellman-ford & SPFA应该也可以再有向图中来判断正环罗？？ 回答一： 因为最短路和最长路的性质不同。 最核心的差异是：最短路随便截一段还是最短路，最长路随便截一段通常不是最长路。 最短路的演算法，就是用上述性质推导出来的。 这个性质就是前面板友所说的 optimal substructure！ 最长路之所以很难算，就是因为我们找不到它的 optimal substructure，只能用穷举法。 回答二： 可以的！在DAG里面，最长路随便截一段就是最长路。 为什麽呢？因为DAG只能傻傻往一个方向前进，不会有绕路、绕圈圈的情形。 有没有正环应该不是主因。 回答三： 可以的！不过并不是你推论的那样。 Bellman-Ford演算法和SPFA都可以判断图上有没有负环。 把图上每条边权重变号，不就可以判断图上有没有正环？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.115.157.18 ※ 编辑: DJWS 来自: 59.115.157.18 (11/02 00:36)