我正在上算法：设计与分析II课，其中一个问题问：
假设p≠NP.考虑具有非负边的无向图长度。下列哪一个问题可以用多项式求解时间
提示：哈密顿路径问题是：给定一个具有n个顶点，决定是否存在具有n的(无循环)路径-1条边，正好访问每个顶点一次。你可以使用这样一个事实，即哈密顿路径问题是NP完全的。相对而言从哈密顿路径问题到4中3的简单约简以下问题。
- 对于给定的源s和目的地t，计算具有n-1条边的最短s-t路径的长度(或+∞，如果没有这样的路径存在)。允许路径包含循环
- 在图的所有生成树中，计算一个叶子数量尽可能少的生成树
- 在图的所有生成树中，计算一个具有最小可能最大度的生成树。(回想一下，顶点的度数是入射边缘的数量。)
- 对于给定的源s和目的地t，计算最短s-t路径的长度，该路径恰好具有n-1条边(或+∞，如果没有这样的路径存在)。路径不允许包含循环
注意，哈密尔顿路径是图的生成树，并且只有两个叶节点，并且图的任何恰好有两个叶结点的生成树都必须是哈密尔顿路径。这意味着，确定图中是否存在哈密顿路径的NP完全问题可以通过找到图的最小叶生成树来解决：该路径存在当且仅当最小叶生成树正有两个叶。因此，问题2是NP完全的。
问题3是NP难问题；这里有一篇论文证明了这一点。
这意味着，在1和4之间，一个是NP完全的，另一个是p。问题4似乎微不足道地简化为哈密顿路径问题，但我不明白有一个循环是如何使其可解的？还是相反？
对于第一个，您可以使用Dijkstra来获得尽可能短的偶数和奇数距离。为此，对于每个顶点，您不需要存储单个最小数，而是需要存储其中的两个。一个是奇数路径的最小权值，另一个是偶数路径的最小权。有了这两个长度后，如果允许循环，可以很容易地将路径长度增加偶数个边。因此，第一个问题来自P。逐步算法是：
- 查找最短的偶数和奇数长度路径
- 通过添加所需次数的长度为2的周期来增加这些路径中具有与
n-1到n-1相同奇偶性的路径之一的长度