我有一个有向、未加权、可能是循环的图，它可以包含循环和多个重复边（即从节点 1 到节点 2 的两条边）。
我现在想找到该图中最长路径的长度，即最长路径： - 两次不使用边（但如果从节点 1 到节点 2 有多条边，则可以使用其中的每一条） - 可能多次访问节点（即它不必是简单的路径）
特别是，这个问题是NP-hard问题吗？我知道最长的简单路径是 NP 难的（减少到它的哈密顿路径），并且具有边重用的最长路径是 P（贝尔曼福特，每条边的权重为 -1）。然而，对于这个问题，我不太确定，也找不到关于它的好的信息。
虽然我不完全确定，但我认为这个问题是NP-hard的。据我了解，您的问题是由于节点之间的多个边而产生的。相同节点之间具有多条边的图可以扩展到它们之间没有多条边的更大图。因此，在相同节点之间具有多条边的图与没有多条边的图没有区别。
让我通过一个简单的例子来解释一下： 假设有一个图，其中有 3 个节点（A、B、C），它们之间有 5 条边（A 到 B、A 到 B、B 到 A、B 到 C、C 到 A） 该图可以展开并显示为 5 个节点和 7 个边。 让我们将节点 A 扩展到 3 个不同的节点（A1、A2、A3）。当我们根据之前的边缘调整边缘时，存在7条边缘（A1到B，A2到B，B到A3，B到C，C到A1，C到A2，C到A3） 结果，现在我们有了一个没有多条边的图，可以在哈密顿量和贝尔曼福特的帮助下进行评估。