在未加权图中查找最长路径

Question

我真的很难解决这个问题。

如果我有一个图形，有向或无向，未加权且没有循环。我如何找到最长的路径？我见过的许多算法都依赖于对图进行加权，并反转权重并使用 bellman ford。我也看过动态规划的解决方案，但这里的人只是在寻找任何路径，我正在寻找来自 s-t 的路径。

我一直在尝试将图分解为子问题，我一次添加一个节点并为其赋予其来自的父节点的值加一，但我无法正确理解逻辑

谁能提供一个算法，指数时间就可以，伪多项式就太棒了？

Answer 1

如果图可以是有向的或无向的，让我们只将问题简化为有向图。如果它是无向的，那么您应该从 v -> w 和 w -> v 生成边。您可以使用修改后的 DFS 来测量从传递给此函数的节点开始的最长路径。然后运行这个函数对每个节点取最大值。

DFS 的伪代码：

DFS(Node v):
  if (v.visited?) return 0;
  v.visited = true;
  longestPath = 0;
  foreach(Node n : v.neighbours):
    longestPath = max(longestPath, DFS(n) + 1)
  return longestPath

问题的伪代码：

longestPath(Node[] verticies):
  longestPath = 0
  foreach(Node v : vertices):
    foreach(Node w: vertices):
      w.visited = false;
    longestPath = max(longestPath, DFS(v))
  return longestPath;

它在 O(n^2) 中有效，但我认为这个解决方案很简单。只是想让你知道，有一个 O(n) 的解决方案。

在未加权图中查找最长路径

Finding the longest path In an unweighted graph

algorithm

path-finding