在没有任何负前缀的图表中查找最短路径

Question

在具有正边缘和负边缘的有向图中找到从源到目的地的最短路径,使得在路径中的任何点处,在其之前的边缘的总和为负.如果不存在这样的路径也报告.

我试图使用改良的Bellman Ford,但找不到正确的解决方案.

---

我想澄清几点:

1. 是的,可以有负重量循环.
2. n是边数.
3. 假设问题有解,则存在O(n)长度路径.
4. + 1/-1边缘权重.

Answer 1

不可否认,这不是一个建设性的答案,但是在评论中发帖太长了......

在我看来,这个问题包含二进制和离散背包问题,所以它的最坏情况运行时间最好是伪多项式.考虑一个连接和加权的图表如下:

然后,等效的二进制背包问题是试图选择从所述权重集{ 一个₀,...,一个_Ñ }最大化Σ  一个_我其中Σ  一个_我 < X.

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

因此,您可能选择的任何实用算法的运行时间取决于您认为的"平均"情况.对于我没有考虑过或者没有考虑过的问题是否存在限制？你似乎很确定这是一个O(n ³)问题.(虽然什么ñ在这种情况下？)

Answer 2

Peter de Rivaz在评论中指出,这个问题包括HAMILTONIAN PATH作为特例.他的解释有点简洁,我花了一些时间来弄清楚细节,所以我画了一些图表,以帮助其他可能正在挣扎的人.我已经发布了这个帖子社区维基.

我将使用以下带有六个顶点的图表作为示例.其中一条汉密尔顿路径以粗体显示.

给定一个具有n个顶点的无向图,我们想要找到哈密顿路径,我们构造一个新的加权有向图,其中有n ²  个顶点,加上START和END顶点.标记原始顶点v _我和新顶点瓦特_IK 0≤  我,  ķ  <  Ñ.如果存在之间的边缘v _我和v _Ĵ在原始图,则对于0≤  ķ  <  Ñ -1有在新的图中的边从瓦特_IK到瓦特_{Ĵ(ķ 1)}与重量-2 ^Ĵ和从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.添加(源,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)