负循环解释的Bellman-ford算法

Question

我尝试实现BF算法的负周期检测。

我跟着备注的讲座来实现算法。我的解决办法如下：

def belman_ford(s, adj, cost):
    arr_len = len(adj)
    dist_arr = [MAX_VAL]*arr_len
    prev_arr = [None]*arr_len
    dist_arr[s] = 0

    for u in range(arr_len):
        for i, v in enumerate(adj[u]):
            if dist_arr[v] == MAX_VAL:
                break
            if dist_arr[v] > dist_arr[u] + cost[u][i]:
                dist_arr[v] = dist_arr[u] + cost[u][i]
                prev_arr[v] = u


    #detect negative cycle
    for u in range(arr_len):
        for i, v in enumerate(adj[u]):
            if dist_arr[v] == MAX_VAL:
                break
            if dist_arr[v] < dist_arr[u] + cost[u][i]:
                return 1

    return 0


def negative_cycle(adj, cost):
    #write your code here
    return belman_ford(0,adj, cost)

然而，我找到了另一个解决方案，帮助我通过编码挑战。

def negative_cycle(adj, cost):
    distance=[0]*len(adj)
    distance[0] = 0
    for ind in range(len(adj)):
        for u in range(len(adj)):
            for v in adj[u]:
                v_index = adj[u].index(v)
                if distance[v] > distance[u] + cost[u][v_index]:
                    distance[v] = distance[u] + cost[u][v_index]
                    if ind==len(adj) - 1:
                        return 1
    return 0

我不明白背后的逻辑。为什么这个if ind==len(adj) - 1 if语句会导致循环检测？

作为输入，我得到了邻接和成本表。

Answer 1

对于Bellman算法的基本思想，下面是来自维基百科的一些快速回顾

Bellman算法简单地放松了所有的边，并执行|V|-1次数，其中|V|是图中的顶点数。

那么您的行if ind==len(adj) - 1的解释是

由于没有循环的最长路径可以是|V|-1边，因此必须对边缘进行扫描|V|-1次数，以确保为所有节点找到最短路径。 完成对所有边的最后扫描，如果任何距离被更新，那么只有在图中存在至少一个负循环时，才能找到长度为|V|边的路径。

行李员-福特起初假设距离很大(无穷大)，然后逐渐把它们降到最低。这叫做放松。在每一次迭代中，距离源更远一步的边缘会得到放松。

S --> A --> B --> C --> D --> E --> F --> G --> H --> I

现在假设你有一个没有负循环的图。假设它有10个顶点，你只需要9次放松就能到达(从源头到)最远顶点的最短路径。如果在9次放松之后你还能得到改善呢？你必须在你的图中有负循环。

代码中的ind是一个计数器。当ind == len(adj) - 1时，它意味着|V|时间有松弛的距离，这说明负循环的存在。

也可以在你自己的笔记中查看最后的第三页。