algorithm - 无向与有向图中的最长路径

Question

我需要解决有向和无向图的最长路径问题（在两种情况下均未加权）。对于有向图，很容易找到能够在伪多项式时间内解决问题的动态规划算法，从某个节点开始，计算子问题的最长路径，直到每个问题都被研究完。

我可以对无向图做类似的事情吗？我似乎找不到任何关于它的文献？

标签： algorithmgraphpath-finding

Answer 1

每个有向图算法都适用于无向图。只需将每条边视为具有相同权重的两条有向边。