如何检查图形是否包含负循环，但无法从源访问它？

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

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

Answer 2

您应该为每个连接的组件运行它。为此，以获取顶点v（在函数中，始终是顶点0）的方式实现函数，然后实现循环，对于距离设置为无穷大的每个顶点，在该顶点上调用函数。