我正在尝试解决在图形中查找最长路径的问题。即使在维基百科中也提到我们正在努力寻找最长的简单路径.
简单路径是没有顶点/边重复的路径。
非简单路径是顶点/边可以重复的路径。我可以将循环或电路视为非简单路径。而且由于电路总是有周期的。
问题：
- 我可以说有向/无向图吗？一条非简单的路径总是有循环？
- 而且因为有循环在非简单路径中，最长的非简单路径或图是不可能的？(就像我们没有算法来为负边图找到最短距离一样？
我在这里错过了什么吗？
你的理解是正确的：一条非简单的路径总是包含一个循环。获取非简单路径上第一个重复节点的第一个实例，并遵循该路径，直到重新访问该节点;那是你的周期！
是的，出于这个原因，图中最长的非简单路径并不总是被定义。事实上，它从未在任何包含至少一条边的图形中定义过。
请注意，在图形中查找最长的简单路径已知是NP-hard的，并且没有已知的有效算法来解决该问题。但是，有一些不错的动态编程解决方案可以减少真正的蛮力运行时间，并且可以使用颜色编码等聪明的算法来有效地找到长路径。