python-3.x - 如何检查图形是否包含负循环但无法从源头到达？

Question

我想检查我的加权图是否有负循环。对于使用 bellman-ford 算法，我们需要选择一个源节点，将所有其他距离初始化为无穷大，如果顶点数为 n，则开始放松 n-1 次。我的问题是无法到达的节点将始终具有无限距离，并且在第 n 次迭代中也不会改变。因此，对于无法到达的负循环，我们会得到错误的输出。

def negative_cycle(adj, cost):
    dist = [float('inf')] * n
    prev = [None] * n
    dist[0] = 0
    for _ in range(n-1):
        for u, edges in enumerate(adj):
            for i, v in enumerate(edges):
                if dist[v]>dist[u]+cost[u][i]:
                    dist[v]=dist[u]+cost[u][i]
                    prev[v]=u
    for u, edges in enumerate(adj):
        for i, v in enumerate(edges):
            if dist[v]>dist[u]+cost[u][i]:
                return 1
    return 0

标签： python-3.xgraphshortest-pathbellman-ford

Answer 1

如果您不关心最短路径而只是想检测负循环，则可以将所有顶点的初始距离设置为 0。这与创建一个虚构的源s并将s连接到所有其他顶点具有相同的效果权重 0 边。

然后，您的代码将如下所示（可能我不懂 Python，所以我的语法可能不正确）。

def negative_cycle(adj, cost):
    dist = [0] * n
    prev = [None] * n
    for _ in range(n-1):
        for u, edges in enumerate(adj):
            for i, v in enumerate(edges):
                if dist[v]>dist[u]+cost[u][i]:
                    dist[v]=dist[u]+cost[u][i]
                    prev[v]=u
    for u, edges in enumerate(adj):
        for i, v in enumerate(edges):
            if dist[v]>dist[u]+cost[u][i]:
                return 1
    return 0