java - 图 - 非简单路径，最长路径

Question

我正在尝试解决在图中查找最长路径的问题。即使在 wikipedia它提到我们正在尝试找到最长的简单路径。

简单路径是没有重复顶点/边的路径。

非简单路径是顶点/边可以重复的路径。我可以将循环或电路视为非简单路径。并且由于电路总是有循环。

问题:

1. 我可以说有向/无向图吗？非简单路径总有环路？
2. 因为非简单路径中存在循环，所以最长的非简单路径或图是不可能的？ (就像我们没有算法来找到具有负边的图的最短距离一样？)

我在这里遗漏了什么吗？

Answer 1

你的理解是正确的:非简单路径总是包含环。获取非简单路径上第一个重复节点的第一个实例，并沿着该路径前进，直到重新访问该节点；这就是你的周期!

是的，由于这个原因，图中最长的非简单路径并不总是被定义。事实上，它从未在任何包含至少一条边的图中定义。

请注意，已知在图中找到最长的简单路径是NP困难的，并且没有已知的有效算法来解决该问题。然而，有一些很好的动态编程解决方案可以减少真正的暴力破解的运行时间，以及像color-coding这样的聪明算法。可用于有效地查找长路径。