我有一个带循环的有向图。关于这个图最重要的部分是，每条边都有一个可以通过多少次的约束，之后它应该变成"；不可用"；。
我该如何找到最长的路？任何信息、链接或评论都将不胜感激。非常感谢。
不幸的是，这个问题是NP完全的，这意味着不太可能存在"快速"；算法(将在多项式时间内解决每个实例的算法(；您需要满足于不能保证找到最佳解决方案的快速启发式，或者使用只能在合理时间内解决小实例的指数时间算法。
我将通过将有向图(HP(中的NP完全问题哈密顿路径简化为您的问题来展示这一点。简单地说，这个想法是：如果存在某种算法，可以解决问题的每一个实例"快速"；(意思是多项式时间(，那么它也可以用作求解HP的每个实例的子程序——这似乎不太可能，因为尽管有几十年的CS研究，但没有人知道如何在多项式时间内求解HP(或任何NP完全问题(。
在HP中，我们得到了一个有向图G=(V，E(，任务是确定是否有一条路径访问所有|V|顶点一次。给定这个问题的一个实例，我们可以构造你的问题的实例G'如下：
- 将每个顶点v替换为三个顶点v_in、v_mid和v_out，将所有入边更改为v，将所有出边从v更改为出边从v_out；称这些边为"；乌木边缘"；(它们对应于G中的边(。还添加从v_in到v_mid以及从v_mid到v_out的边；称这些边为"；天鹅绒边缘"；(它们对应于G中的顶点(
- 为每条边指定1的通过限制
此图中存在长度为3|V|-1的路径当且仅当原始图G:中存在Hamiltonian路径
"；如果"；方向：假设G包含一个哈密顿路径。这对应于所构建的图中长度为3|V|-1的路径，该路径以一对天鹅绒边开始和结束，并在天鹅绒边和乌木边之间交替，图案为VVEVVE。。。EVV。
"；只有当"；方向：假设在构造的图中存在长度为3|V|-1的路径P。每条边的通过限制为1，因此每条边在此路径中最多出现一次。P必须具有以下边缘模式之一：
- VVEVVE。。。EVV
- VEVVE。。。EVVE
- EVVE。。。EVVEV
在每种情况下，p遍历与G中的每个顶点对应的两个天鹅绒边中的至少一个，因此对应于G中的哈密顿路径。