graph - 最宽路径和最长路径问题之间的根本区别

Question

最宽路径和最长路径问题之间有什么区别？更具体地说，为什么前者可以通过找到最大生成树来解决，而后者却不能。我知道在画出最大生成树时，很明显它不一定包含最长的路径，但我无法理解这两个问题之间的差异是什么，这两个问题是真实的。

谢谢。

Answer 1

这两个问题之间的主要区别在于，最宽路径问题表现出最优子结构，而最长路径问题（据任何人所知）没有。

具体来说，考虑从节点 u 到节点 v 的最宽路径。如果该路径通过中间节点 s，那么从 u 到 v 的最宽路径必须由从 u 到 s 的最宽路径和从 s 的最宽路径组成到 v。如果没有，那么您可以用更宽的路径替换从 u 到 s 或从 s 到 v 的路径的任何一部分，而不会使解决方案变得更糟。

但是，这不适用于最长路径问题。如果您采用从 u 到 v 的最长路径（隐含地，最长的简单路径）并且它通过一些节点 s，那么您不一定有从 u 到 s 的最长路径，然后是从 s 到 v 的最长路径。这是一个例子：

   2
u --- v
1 \ / 3
   s

从 u 到 s 的最长路径是路径 u - v - s（长度为 5），而从 u 到 v 的最长路径是 u - s - v（长度为 4）。

这种最优的子结构特性使得使用贪心算法和（有效的）动态规划来有效地解决最宽路径问题成为可能，但（据任何人所知）不可能有效地解决最长路径问题。顺便说一下，您可以就最短路径提出类似的论点（如果从 u 到 v 的最短路径经过 s，则您有从 u 到 s 和从 s 到 v 的最短路径的串联），并且您可以使用类似的贪心算法或 DP 也可以确定最短路径。

希望这可以帮助！