algorithm - 在图中找到没有任何负前缀的最短路径

Question

在具有正边和负边​​的有向图中找到从源到目的地的最短路径，使得在路径中的任何一点，在它之前的边的总和都是负的。如果不存在这样的路径，也请报告。

我尝试使用改装的贝尔曼福特，但找不到正确的解决方案。

---

我想澄清几点：

1. 是的，可能会有负重循环。
2. n 是边数。
3. 如果问题有解决方案，则假设存在 O(n) 长度路径。
4. +1/-1 边缘权重。

Answer 1

诚然，这不是一个建设性的答案，但是在评论中发布太长了......

在我看来，这个问题包含二进制和离散背包问题，所以它的最坏情况运行时间充其量是伪多项式。考虑如下连接和加权的图：

然后等价的二元背包问题试图从集合 { a ₀ , ..., a _n } 中选择权重，使 Σ  a _i最大化，其中 Σ  a _i < X。

作为旁注，如果我们引入加权循环，则很容易构建无界背包问题。

因此，您可能选择的任何实用算法的运行时间取决于您认为的“平均”情况。对我没有考虑或无法处理的问题是否有限制？您似乎很确定这是一个 O( n ³ ) 问题。（尽管在这种情况下n是什么？）

Answer 2

Peter de Rivaz在评论中指出，这个问题包括作为特例的HAMILTONIAN PATH 。他的解释有点简洁，我花了一段时间才弄清楚细节，所以我画了一些图表，以帮助其他可能遇到困难的人。我已经制作了这个帖子社区维基。

我将使用下图的六个顶点作为示例。其中一条哈密顿路径以粗体显示。

给定一个有n个顶点的无向图，我们要为其找到一条哈密顿路径，我们构造一个具有n ² 个顶点以及 START 和 END 顶点的新加权有向图。为 0 ≤ <em>i,  _k <  n 标记原始顶点vi和新顶点w _ik。如果原始图中 在v _i和v _j之间存在边，那么对于 0 ≤ <em>k < n -1，在新图中存在从w _ik到w _{j ( k +1)}且权重为 -2的边^j从w _jk到w _{i ( k +1)}，权重为 -2 ⁱ。从 START 到w _i0的边的权重为 2 ⁿ  - 2 ⁱ  - 1，从w _{i ( n -1)}到 END 的边的权重为 0。

最容易认为这种结构等同于以 2 ⁿ  - 1 的分数开始，然后每次访问w _{ij时减去 2} ⁱ。（这就是我绘制下图的方式。）

从 START 到 END 的每条路径必须恰好访问n  + 2 个顶点（每行一个，加上 START 和 END），因此沿路径的总和为零的唯一方法是它只访问每一列一次。

因此，这里是具有六个顶点的原始图转换为具有 38 个顶点的新图。原始哈密顿路径对应于粗体绘制的路径。您可以验证沿路径的总和是否为零。

Answer 3

更新： OP现在已经进行了几轮澄清，现在是一个不同的问题。我将把它留在这里以记录我对问题的第一个版本的想法（或者更确切地说是我对它的理解）。我会为当前版本的问题尝试一个新的答案。 更新结束

遗憾的是，OP 没有澄清一些悬而未决的问题。我将假设以下内容：

1. 权重为 +/- 1。
2. n 是顶点数

显然，第一个假设不失一般性，但它对 n 的值有很大影响（通过第二个假设）。如果没有第一个假设，即使是一个很小的（固定的）图也可以通过无限制地改变权重来获得任意长的解。

我提出的算法非常简单，类似于著名的图算法。虽然我不是图表专家，所以我可能在某些地方使用了错误的词。随时纠正我。

1. 对于源顶点，记住成本 0。将 (source, 0) 添加到待办事项列表中。
2. 从待办事项列表中弹出一个项目。跟随顶点的所有出边，计算新成本 c 以到达新顶点 v。如果新成本有效（c >= 0和 c <= n ^ 2，见下文）并且没有记住 v，则添加它到记住的 v 的成本值，并将 (v, c) 添加到您的待办事项列表中。
3. 如果待办事项列表不为空，则继续第 2 步。（如果可以使用成本 0 到达目的地，则提前中断）。

很明显，不是直接死胡同的每个“步骤”都会创建一个新的（顶点，成本）组合。这些组合最多会存储 n * n ^2 = n ^ 3 个，因此，从某种意义上说，这个算法是 O(n^3)。

现在，为什么这会找到最佳路径？我没有真正的证明，但我认为以下想法证明了为什么我认为这就足够了，并且它们有可能变成真正的证明。

我认为很明显，我们唯一需要证明的是条件 c <= n ^ 2 就足够了。

首先，让我们注意任何（可达）顶点都可以以小于 n 的成本到达。

令 (v, c) 成为最优路径的一部分并且 c > n ^ 2。由于 c > n，在到达 (v, c) 之前，路径上必须存在一些循环，其中循环的成本为 0 < m1 <n，到达(v,c)后的路径上必然存在某个循环，其中循环的代价为0 > m2 > -n。

此外，让 v 可以从成本 0 <= c1 < n 的源到达，通过一条触及上述第一个循环的路径，并让目的地可以从成本 0 <= c2 < n 的 v 到达，通过一条路径触及上面提到的另一个循环。

然后我们可以构建从源到 v 的路径，成本为 c1, c1 + m1, c1 + 2 * m1, ...，以及从 v 到目的地的路径，成本为 c2, c2 + m2, c2 + 2 * m2, ... . 选择 0 <= a <= m2 和 0 <= b <= m1 使得 c1 + c2 + a * m1 + b * m2 最小，因此最优路径的成本。在这条最优路径上，v 的成本为 c1 + a * m1 < n ^ 2。

如果 m1 和 m2 的 gcd 为 1，则成本为 0。如果 gcd > 1，则可以选择其他循环使 gcd 变为 1。如果不可能，也不可能对于最优解，最优解会有正成本。

（是的，我可以看到这种尝试证明的几个问题。可能有必要采用几个正或负循环成本等的 gcd。不过，我会对反例非常感兴趣。）

这是一些（Python）代码：

def f(vertices, edges, source, dest):
    # vertices: unique hashable objects
    # edges: mapping (u, v) -> cost; u, v in vertices, cost in {-1, 1}

    #vertex_costs stores the possible costs for each vertex
    vertex_costs = dict((v, set()) for v in vertices)
    vertex_costs[source].add(0) # source can be reached with cost 0

    #vertex_costs_from stores for each the possible costs for each vertex the previous vertex
    vertex_costs_from = dict()

    # vertex_gotos is a convenience structure mapping a vertex to all ends of outgoing edges and their cost
    vertex_gotos = dict((v, []) for v in vertices)
    for (u, v), c in edges.items():
        vertex_gotos[u].append((v, c))

    max_c = len(vertices) ** 2 # the crucial number: maximal cost that's possible for an optimal path

    todo = [(source, 0)] # which vertices to look at

    while todo:
        u, c0 = todo.pop(0)
        for v, c1 in vertex_gotos[u]:
            c = c0 + c1
            if 0 <= c <= max_c and c not in vertex_costs[v]:
                vertex_costs[v].add(c)
                vertex_costs_from[v, c] = u
                todo.append((v, c))

    if not vertex_costs[dest]: # destination not reachable
        return None # or raise some Exception

    cost = min(vertex_costs[dest])

    path = [(dest, cost)] # build in reverse order
    v, c = dest, cost
    while (v, c) != (source, 0):
        u = vertex_costs_from[v, c]
        c -= edges[u, v]
        v = u
        path.append((v, c))

    return path[::-1] # return the reversed path

以及一些图的输出（路径的每个点的边缘及其权重/路径/成本；抱歉，没有漂亮的图像）：

AB+ BC+ CD+ DA+             AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-
 A  B  C  D  A  X  Y  H  I  J  K  L  M  H
 0  1  2  3  4  5  6  7  6  5  4  3  2  1
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-
 A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  X  Y  H  I  J  K  L  M  H  I  J  K  L  M  H  I  J  K  L  M  H  I  J  K  L  M  H
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-
 A  X  Y  H
 0  1  2  3
AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-
 A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  B  C  D  E  F  G  A  X  Y  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H  I  J  K  L  M  N  O  P  H
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

这是产生该输出的代码：

def find_path(edges, source, path):
    from itertools import chain

    print(edges)
    edges = dict(((u, v), 1 if c == "+" else -1) for u, v, c in edges.split())
    vertices = set(chain(*edges))

    path = f(vertices, edges, source, dest)
    path_v, path_c = zip(*path)
    print(" ".join("%2s" % v for v in path_v))
    print(" ".join("%2d" % c for c in path_c))

source, dest = "AH"

edges = "AB+ BC+ CD+ DA+             AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-"
# uv+ means edge from u to v exists and has cost 1, uv- = cost -1
find_path(edges, source, path)

edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MH-"
find_path(edges, source, path)

edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NH-"
find_path(edges, source, path)

edges = "AB+ BC+ CD+ DE+ EF+ FG+ GA+ AX+ XY+ YH+ HI- IJ- JK- KL- LM- MN- NO- OP- PH-"
find_path(edges, source, path)

Answer 4

正如 Kaganar 所指出的，我们基本上必须做出一些假设才能获得多时间算法。假设边长在 {-1, 1} 中。给定该图，构造一个加权的上下文无关文法，该文法识别从源到目的地的有效路径，其权重等于多余 1 条边的数量（它概括了平衡括号的文法）。对于每个非终结符，通过将所有内容初始化为无穷大或 1 来计算最便宜生产的成本，具体取决于是否存在 RHS 没有非终结符的生成，然后放宽 n - 1 次，其中 n 是非终结符的数量。

Answer 5

尽管人们已经证明不存在快速解决方案（除非 P=NP）..

我认为对于大多数图表 (95%+)，您应该能够相当快地找到解决方案。

我利用了这样一个事实，即如果有循环，那么通常会有很多解决方案，我们只需要找到其中一个。我的想法中可能有一些明显的漏洞，所以请告诉我。

Ideas:

1.找到离目的地最近的负循环。将循环和目的地之间的最短距离表示为 d(end,negC)

（我认为这是可能的，一种方法可能是使用 floyds 检测具有负循环的 (i,j)，然后从目的地进行广度优先搜索，直到遇到与负循环相关的东西。）

2.找到离起始节点最近的正循环，表示到起始点的距离为d(start,posC)

（我认为在 95% 的图表中，您可以轻松找到这些循环）

    Now we have cases:
a) there is both the positive and negative cycles were found:
The answer is d(end,negC).

b) no cycles were found:
simply use shortest path algorithm?

c) Only one of the cycles was found. We note in both these cases the problem is the same due to symmetry (e.g. if we swap the weights and start/end we get the same problem). I'll just consider the case that there was a positive cycle found.

find the shortest path from start to end without going around the positive cycle. (perhaps using modified breadth first search or something). If no such path exists (without going positive).. then .. it gets a bit tricky.. we have to do laps of the positive cycle (and perhaps some percentage of a lap).
If you just want an approximate answer, work out shortest path from positive cycle to end node which should usually be some negative number. Calculate number of laps required to overcome this negative answer + the distance from the entry point to the cycle to the exit point of the cycle. Now to do better perhaps there was another node in the cycle you should have exited the cycle from... To do this you would need to calculate the smallest negative distance of every node in the cycle to the end node.. and then it sort of turns into a group theory/ random number generator type problem... do as many laps of the cycle as you want till you get just above one of these numbers.

祝你好运，希望我的解决方案适用于大多数情况。

Answer 6

我想澄清几点：

1. 是的，可能会有负重循环。
2. n 是边数。
3. 权重是任意的，而不仅仅是 +1/-1。
4. 如果问题有解决方案，则假设存在 O(n) 长度路径。（n 是边数）

Answer 7

目前的假设是：

1. 是的，可能会有负重循环。
2. n 是边数。
3. 如果问题有解决方案，则假设存在 O(n) 长度路径。
4. +1/-1 边缘权重。

我们可以不失一般性地假设顶点的数量最多为 n。递归遍历图并记住每个顶点的成本值。如果已经为顶点记住了成本，或者成本是负数，则停止。

在 O(n) 步之后，要么没有到达目的地，要么没有解决方案。否则，对于每个 O(n) 个顶点，我们最多记住 O(n) 个不同的成本值，并且对于这些 O(n ^ 2) 个组合中的每一个，可能有多达 n 次不成功的尝试步行到其他顶点. 总而言之，它是 O(n ^ 3)。qed

更新：当然，还有一些可疑的东西。假设 3 是什么意思：如果问题有解决方案，则存在 O(n) 长度路径？任何解决方案都必须检测到这一点，因为如果没有解决方案，它也必须报告。但是不可能检测到这一点，因为这不是算法所处理的单个图的属性（它是渐近行为）。

（同样清楚的是，并非所有可以到达目的地的图都具有长度为 O(n) 的解路径：取一条由 m 条边组成的链，其权重为 -1，在此之前，有 m 个边和总权重的简单循环+1）。

[我现在意识到我的其他答案（尝试问题的第一个版本）中的大部分 Python 代码都可以重用。]

Answer 8

我会在这里使用递归暴力破解：类似于（伪代码以确保它不是特定于语言的）

你会需要：

• 二维布尔数组显示你可以去哪里和你不能去哪里，这不应该包括“禁止值”，就像在负边缘之前，你可以选择添加一个垂直和水平的“平移”以确保它从 [0 ][0]
• 包含最短路径的整数（静态）
• 2 个插槽的一维数组，显示目标。[0] = x, [1] = y

你会去做的：

function(int xPosition, int yPosition, int steps)
{
if(You are at target AND steps < Shortest Path)
    Shortest Path = steps
if(This Position is NOT legal)
    /*exit function*/
else
    /*try to move in every legal DIRECTION, not caring whether the result is legal or not
    but always adding 1 to steps, like using:*/
    function(xPosition+1, yPosition, steps+1);
    function(xPosition-1, yPosition, steps+1);
    function(xPosition, yPosition+1, steps+1);
    function(xPosition, yPosition-1, steps+1);
}

然后用 function(StartingX, StartingY, 0) 运行它；

最短路径将包含在静态外部 int 中

Answer 9

第 1 步：请注意，您的答案最多为 2*n（如果存在）。
第 2 步：创建一个新图，其顶点是一对 [vertex][cost]。（2*n^2 个顶点）
第 3 步：请注意，新图的所有边都等于 1，并且每个 [vertex][cost] 对最多有 2*n。
第 4 步：对该图执行 dfs，从 [start][0] 开始
第 5 步：找到最小 k，使得 [finish][k] 是可访问的。

总复杂度最多为 O(n^2)*O(n) = O(n^3)

编辑：第 1 步的澄清。
如果有一个正循环，从一开始就可以访问，你可以一直到 n。现在你可以走到任何可访问的顶点，不超过 n 条边，每条边都是 +1 或 -1，留下 [0;2n] 范围。否则，您将经历不处于负循环的负循环或不超过 n +1 的负循环，从而为您留下 [0;n] 范围。