一个特定类型的图中的最长路径

Question

我知道 最长路径问题 对于一般图来说是 NP 难的。然而，我正在考虑一种特殊类型的图，它由一个环和每个顶点上的一个额外边组成。例如，对于长度为7的环，我们有以下图形：

所有的边都有权值（权值是实数，可以是正数或负数）。我想在这个图上找到最长的简单路径，其中路径的大小是路径上边的权值之和。

算法应该是线性的循环大小。但是任何想法都会受到赞赏。

- a06e

---

这肯定是从图中修剪死胡同，然后找到最低权重的边，并使用它的两端作为最长（最高加权）链的起点和终点的情况。 - paddy

@paddy：如果权重不能为负数，那么这个方法就可行了... - Oliver Charlesworth

@paddy：我不是很明白，请你能具体一点吗？ - a06e

@becko：那 会 改变问题；结果的偏移量将与路径中的边数成比例。 - Oliver Charlesworth

@becko 嗯，检查配对的朴素算法将是 O(N^3)。你需要预处理循环以在 O(1) 中获取两点之间的距离。 - Sergey Kalinichenko

Answer 1

这可以转化为最大子数组问题，并在线性时间内解决。

1. 断开环路（在任何一个节点处）。
2. 将剩余图的第二份拷贝附加到断开环路的点上（我们可以跳过最后一个节点）。
3. 对得到的节点列表应用修改后的Kadane算法。
4. 如果找到的路径没有边，则搜索图中权重最大的边。如果这条边具有非负权重，则报告此单边路径。如果不是，则无论是否允许空路径，仍然报告此单边路径，或者报告空路径。

->

Kadane算法的必要修改：

1. 跟踪当前路径（子数组）中的节点数量。当子数组具有N个或更多的“循环”节点时，从尾部修剪节点。为了高效地修剪这些节点，我们需要一个可以报告其元素最小值的队列。每当路径头被推进（如果非负，则添加叶边权重），则将元素推送到此队列中，当路径尾部被修剪时则弹出元素，并在当前路径被重置为空路径时重置队列。该队列包含（不一定是简单）路径的前缀长度，其中最小值给出了推进路径尾部的正确位置。这样的队列可以实现为只持有非递减值的双端队列，或如这个回答中提到的一堆堆。
2. 无论何时，如果当前路径长度低于零，则将路径长度重置为max(0, leaf_edge_weight)（而不是像Kadane算法原始版那样将其重置为零）。
3. 在将当前（非空）路径与迄今为止的最佳路径进行比较时，添加非负叶边权重（对应于头节点）。

- Evgeny Kluev

---

我也正准备回答这个问题 :) 但是我还没有想好如何在子数组节点数超过N个时高效地从尾部修剪节点。你能详细说明一下吗？ - j_random_hacker

@j_random_hacker：这部分肯定需要更多的解释。谢谢。 - Evgeny Kluev

Answer 2

在环上选择一个链接。最长路径要么通过该链接，要么不通过该链接，因此让我们在这两种情况下找出最佳答案，并选择其中最好的。

如果最长路径不通过循环链接，则删除链接以生成一棵树。从叶子节点向上工作，在每个节点处计算该节点下的最长路径和从该节点到任何后代的最长路径。在每个节点处，您可以通过查看其子节点的答案来计算答案。根节点处的答案给出了最长路径。

如果最长路径确实经过您选择的链接，则它必须由从链接的一端顺时针走的部分和从链接的另一端逆时针走的部分组成。这两个部分的长度加起来不超过用于构成循环的链接数加一。对于i = 1到限制，计算出从链接的每一侧顺时针和逆时针路径的成本，并保持运行的最大值。通过链接的最长路径的长度是最长路径的总和，对于某些k，该路径顺时针走k个链接并逆时针走N-k个链接（如果存在类似成本的-ve链接成本，则可能需要进行一些调整）。因此，您可以找到经过您选择的链接的最长路径，成本也为O(n)。

计算成本为O(n)的两种情况，并选择最佳情况，总成本为O(n)。

- mcdowella

---

你有考虑负权重吗？如果在所选节点和最长路径之间存在一些带有巨大负权重的边，会怎样呢？它将找到与节点相同侧的最长路径（而不是全局最长路径）。 - Bernhard Barker

当你说“您可以通过选择任意节点作为根节点并查看最长路径来展示这一点，该路径必须通过根节点”时，您是否只是指“通过根节点的最长路径”？ 因为整体树中最长的路径不一定要经过某个随意选择的根（毕竟只是随意选择的顶点）。 但是在这种情况下，您的论点似乎无法解释为什么将找到最长的全局路径 - “半路径”似乎是相对于所选择的根。 该算法似乎是可行的，但我还不明白为什么它必须有效！ - j_random_hacker

@Dukeling，我在树的负权重情况下犯了错误。我已经用有向无环图的解决方案替换了该部分。 - mcdowella

@j_random_hacker 我无法重构一个我被告知的事实的证明 - 至少在正权重的情况下。我被告知想象通过选择的第一个点来支撑树。最长路径两端的两个点中至少有一个必须从那里垂下，距离它至少为最长路径的一半。如果存在比这两个点更远的点，则可以将其与所谓的最长路径结合使用以创建更长的路径，这是矛盾的。 - mcdowella

@Dukeling - 哎呀，树不是有向的，所以我又对树的情况进行了尝试。 - mcdowella

Answer 3

最长路径几乎肯定在外部两个顶点之间。而且几乎肯定需要覆盖循环中的所有顶点。

因此，您希望使用DFS在O（N）内绘制出循环。然后计算当前循环排列的长度。将第一个点到其外部的距离和最后一个点到其外部的距离加到该长度中。这就给出了实际路径长度，您可以将其与循环长度分开存储。

增加第一个点和最后一个点的索引（可以在O（1）内完成），删除现在从第一个点到最后一个点的有向边的长度。然后再次添加外部长度。重复此过程，直到覆盖所有顶点。由于您存储并更新路径长度而不是每次重新计算它（这将需要O（N ^ 2）），因此可以在O（N）内完成。

这允许在O（N）内遍历循环。但是，这不是精确算法。这要求检查是否应该使用第一个+i和/或last-j代替某些i，j。要完全检查这一点，基本上需要O（N ^ 2）。

尽管如此，通过巧妙地确定可能存在这些边缘情况的位置，您可能会在大约O（N log N）内完成。我怀疑是否可能存在精确的线性算法。

- Nuclearman