: 回答一： : 因为最短路和最长路的性质不同。 : 最核心的差异是：最短路随便截一段还是最短路，最长路随便截一段通常不是最长路。 : 最短路的演算法，就是用上述性质推导出来的。 : 这个性质就是前面板友所说的 optimal substructure！ : 最长路之所以很难算，就是因为我们找不到它的 optimal substructure，只能用穷举法。 : 回答二： : 可以的！在DAG里面，最长路随便截一段就是最长路。 : 为什麽呢？因为DAG只能傻傻往一个方向前进，不会有绕路、绕圈圈的情形。 : 有没有正环应该不是主因。 : 回答三： : 可以的！不过并不是你推论的那样。 : Bellman-Ford演算法和SPFA都可以判断图上有没有负环。 : 把图上每条边权重变号，不就可以判断图上有没有正环？ 补充一下 在允许负边, 比较general的graph上, 最长路和最短路的性质其实是一样,对称的 在这样的graph上 longest 'simple' path和 shortest 'simple' path同样是np-hard longest path和shortest path(不要求simple)都是 in P 之前几篇文指的最长路应该都是指'最长简单路', 需要强调一下 正环和负环性质都是对称的, 直接用bellman-form找最长路就可以测正环的存在 --

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