我有一个有向的、未加权的、可能是循环的图，它可以包含循环和多个重复边（即从节点 1 到节点 2 的两条边）。
我现在想找到该图中最长路径的长度，即最长路径： - 两次不使用边（但如果从节点 1 到节点 2 有多个边，它可以使用其中的每一个） -可能多次访问节点（即它不必是简单的路径）
特别是，这个问题是 NP 难的吗？我知道最长的简单路径是 NP 难的（减少哈密顿路径），并且边缘重用的最长路径在 P 中（贝尔曼福特，每条边的权重为 -1）。但是，对于这个问题，我不太确定，也找不到很好的信息。
问问题
558 次
1 回答
1
Although I am not completely sure, I think that this problem is NP-hard. As I understand, your question arises due to multiple edges between nodes. The graphs that has multiple edges between same nodes can be expanded to larger graphs with no multiple edges between them. Thus, a graph with multiple edges between same nodes has no difference than a graph without multiple edges.
Let me walkthrough a simple example to explain: Let there be a graph with 3 nodes (A,B,C) and 5 edges between them (A to B, A to B, B to A, B to C, C to A) This graph can be expanded and shown with 5 nodes and 7 edges. Lets expand the node A to 3 different nodes (A1, A2, A3). When we adjust the edges according to previous edges, there exists 7 edges(A1 to B, A2 to B, B to A3, B to C, C to A1, C to A2, C to A3) As a result, now we have a graph without multiple edges and can be evaluated with the help of Hamiltonian and Bellman Ford.
Hope I've at least cleared the problem a bit.
于 2014-09-04T10:25:57.513 回答