我正在尝试解决在图中找到最长路径的问题。即使在wikipedia中也提到了我们正在尝试找到longest simple path。
简单路径是没有顶点/边重复的路径。
非简单路径是顶点/边可以重复的路径。我可以将循环或电路视为非简单路径。而且由于电路总是有循环的。
问题：
我在这里想念什么吗？
您的理解是正确的：非简单路径将始终包含一个循环。在非简单路径上获取第一个重复节点的第一个实例，并按照路径进行操作，直到重新访问该节点为止；那是你的周期！
并且是的，因此并非总是定义图中最长的非简单路径。实际上，从来没有在任何包含至少一条边的图形中定义它。
注意，在图中找到最长的路径已知是[[NP]]-难的，并且没有已知的有效算法可以解决该问题。但是，有一些不错的动态编程解决方案可以减少真正的蛮力运行时间，并且可以使用像color-coding这样的聪明算法来稍微有效地查找长路径。