图 - 非简单路径，最长路径
Graph - Non Simple Path , Longest Path
我正在尝试解决在图形中寻找最长路径的问题。即使在 wikipedia 中也提到我们试图找到 longest simple path 。
简单路径 是没有 vertices/edges 重复的路径。
非简单路径 是 vertices/edges 可以重复的路径。我可以将循环或电路视为非简单路径。而且由于电路总是有循环的。
问题：
- 我可以说 directed/un-directed 图吗？一条非简单路径总是有循环？
- 并且因为非简单路径中存在循环，最长的非简单路径或图形是不可能的？ （就像我们没有算法可以找到负边图的最短距离？）
我在这里遗漏了什么吗？
您的理解是正确的：非简单路径总是包含一个循环。获取非简单路径上第一个重复节点的第一个实例，并沿着路径前进，直到您重新访问该节点；这就是你的周期！
是的，因此并不总是定义图中最长的非简单路径。事实上，它从未在包含至少一条边的任何图形中定义。
请注意，已知在图中寻找最长的简单路径是 NP-hard，并且目前还没有解决该问题的有效算法。但是，有一些不错的动态编程解决方案可以减少真正的蛮力运行时间，并且可以使用像 color-coding 这样的聪明算法来稍微有效地找到长路径。
我正在尝试解决在图形中寻找最长路径的问题。即使在 wikipedia 中也提到我们试图找到 longest simple path 。
简单路径 是没有 vertices/edges 重复的路径。
非简单路径 是 vertices/edges 可以重复的路径。我可以将循环或电路视为非简单路径。而且由于电路总是有循环的。
问题：
- 我可以说 directed/un-directed 图吗？一条非简单路径总是有循环？
- 并且因为非简单路径中存在循环，最长的非简单路径或图形是不可能的？ （就像我们没有算法可以找到负边图的最短距离？）
我在这里遗漏了什么吗？
您的理解是正确的：非简单路径总是包含一个循环。获取非简单路径上第一个重复节点的第一个实例，并沿着路径前进，直到您重新访问该节点；这就是你的周期！
是的，因此并不总是定义图中最长的非简单路径。事实上，它从未在包含至少一条边的任何图形中定义。
请注意，已知在图中寻找最长的简单路径是 NP-hard，并且目前还没有解决该问题的有效算法。但是，有一些不错的动态编程解决方案可以减少真正的蛮力运行时间，并且可以使用像 color-coding 这样的聪明算法来稍微有效地找到长路径。