我有一个有向的，未加权的，可能是循环的图，它可以包含循环和多个重复边（即从节点1到节点2的两条边） .
我现在想在这个图中找到最长路径的长度，即最长路径： - 不使用两次边缘（但如果从节点1到节点2有多个边缘，它可以使用它们中的每一个） - 可能会多次访问节点（即它不必是一个简单的路径）
特别是这个问题NP难吗？我知道最长的简单路径是NP-hard（减少汉密尔顿路径），最长的边缘拒绝路径是P（Bellman ford，每个边缘的权重为-1） . 但是，有了这个问题，我不太确定，我找不到有关它的好信息 .
1 回答
虽然我不完全确定，但我认为这个问题很难实现 . 据我了解，您的问题是由于节点之间的多个边缘引起的 . 在相同节点之间具有多个边的图可以扩展为更大的图，它们之间没有多个边 . 因此，在相同节点之间具有多个边缘的图形与没有多个边缘的图形没有区别 .
让我演练一个简单的例子来解释：让图中有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）结果，现在我们有没有多个边缘的图形，可以在Hamiltonian和Bellman Ford的帮助下进行评估 .
希望我至少能解决这个问题 .