python - 有向图中的最大简单循环

Question

图中的最大简单循环(乘积)

你好，

我构建了一个有向图 G=(v,e)，我想找到该图中的最大简单循环，其中边权重相乘而不是相加。我最初的方法是构造一个新图 G=(v,e')，其中 e'(i,j) = 1/e(i,j)/min(e')，然后应用Floyd-Warshall 在此图上查找所有最短路径。我的想法是，反转图形后，最大路径将变为最小值，如果我们除以最小值，所有边权重将是“正”(>= 1，因为我们是乘法而不是加法)。但是，当我运行该算法(我的 Python 代码如下)时，它似乎不起作用，我想知道这是因为我的算法根本不起作用还是因为我的代码中存在错误。

#construct G' = (V,dist) for our modified Floyd-Warshall algorithm
# edge weights are initially the inverse of w(u,v). They are then all divided
# by the minimum value to ensure all are >= 1
dist = {}
nxt = {}
minimum = float("inf")
for i in e:
    dist[i] = {}
    nxt[i] = {}
    for j in e[i]:
        dist[i][j] = 1/e[i][j]
        nxt[i][j] = j
        if dist[i][j] < minimum:
            minimum = dist[i][j]

for i in dist:
    for j in dist[i]:
        dist[i][j] /= minimum

# Perform Floyd-Warshall
for k in v:
    for i in v:
        for j in v:
            try:
                one = dist[i][j]
                two = dist[i][k]
                three = dist[k][j]
            except KeyError:
                continue

            if one > two * three:
                dist[i][j] = two * three
                nxt[i][j] = nxt[i][k]

# Find the shortest cycle using shortest paths
minimum = float("inf")
for i in v:
    for j in v:
        if i == j:
            continue
        try:
            one = dist[i][j]
            two = dist[j][i]
        except KeyError:
            continue

        if one * two < minimum:
            minimum = one * two
            pair = [i,j]

def Path(u,v):
    if nxt[u][v] == None:
        return []
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path

# Format the cycle for output
p1 = Path(pair[0],pair[1])
p2 = Path(pair[1],pair[0])
p = p1 + p2[1:]
print(p)

# Find the total value of the cycle
value = 1
for i in range(len(p)-1):
    value *= e[p[i]][p[i+1]]

print('The above cycle has a %f%% weight.'  % ((value-1)*100))

我用图 G=(V,E) 测试了上面的示例，其中

V = {a,b,c,d}, and 
E = {
    (a,b): 1/0.00005718 * 0.9975, 
    (a,c): 1/0.03708270 * 0.9975,
    (a,d): 18590.00000016 * 0.9975, 
    (b,a): 0.00010711 * 0.9975,
    (b,c): 0.00386491 * 0.9975, 
    (c,a): 0.03700994 * 0.9975,
    (c,b): 1/18590.00000017 * 0.9975,
    (c,d): 688.30000000 * 0.9975,
    (d,a): 1/18590.00000017 * 0.9975,
    (d,c): 1/688.30000000 * 0.9975
}

上图的输出结果是循环[a,d,a]是最好的，权重为86.385309%。然而，正如我们所看到的，循环[a,b,c,a]的权重为148.286055%，这要好得多，这让我相信要么我的算法是错误的，要么我有某处出现错误。

非常感谢任何建议!!

Answer 1

我认为问题不在于实现，而在于算法。实际上，采用以下示例，其中包含四个顶点 a、b、c 和 d，以及以下边:

w(a,b)=10/3

w(b,c)=10

w(c,d)=5

w(d,a)=10/3

w(d,b)=5

然后，您的算法将返回有向循环 (b,c,d,b)，而最佳解决方案是 (a,b,c,d,a)。

此外，您还应该知道您的问题可能是 NP 完全问题，因为 Longest Path problem是 NP 完全的(即使最短路径问题 是多项式可解的)，因此只有少数人希望有一个如此简单的算法来解决您的问题。