判断带权有向图中是否存在任意大权重路径的时间复杂度问题

嘿，你的困惑我太懂了——明明都说最长路径是NP难问题，为啥这个判断问题的答案却是O(n³)？其实关键在于：这个问题和“寻找最长路径”完全不是一回事！

先拆解问题本质 #

我们要判断的是“是否存在权重能无限变大的路径”，这件事的核心等价于：图里有没有一个正权的有向环，而且这个环是能被遍历到的（也就是说，能从某个节点走到这个环，也能从环走到其他节点）。

为啥这么说？因为只要有这么个正权环，我们就可以在路径里绕它无数次——每绕一圈，路径总权重就加一次环的正权重，绕得越多权重越大，自然能变得任意大。而咱们常说的“最长路径问题”，是找不重复节点的简单路径的最大权重，那才是NP难的——毕竟不能重复绕环，得走不同节点，复杂度天差地别。

对应的算法和时间复杂度 #

要检测这种正权环，常用的两种算法都能达到O(n³)的时间复杂度：

• Bellman-Ford算法：
  它的思路是，如果图里有正权环，那做完n-1次松弛操作后，还能继续松弛某些边（毕竟绕环一次就能让路径权重更大）。它的时间复杂度是O(n*m)，如果是稠密图（边数m差不多是n²），那就是O(n³)了。
• Floyd-Warshall算法：
  这个算法是用来算所有节点对之间的最长路径的，如果某个节点i的d[i][i] > 0，就说明存在从i到i的正权环。它的时间复杂度固定是O(n³)，不管图是稠密还是稀疏。

题目给的选项里O(n³)是正确答案，就是因为稠密图下Bellman-Ford会达到这个复杂度，而Floyd-Warshall本身就是O(n³)，这俩方法都能搞定这个判断问题。

一句话总结 #

别把“判断是否有无限增重的路径”和“找最长简单路径”搞混啦：后者是NP难，但前者只需要检测正权环，而检测正权环的算法是多项式时间的，O(n³)就是符合要求的正确选项。

内容的提问来源于stack exchange，提问作者Geeklovenerds