负循环解释的 Bellman-ford 算法

Question

我尝试实现负循环检测的 BF 算法。

我跟着讲座notes实现了算法。我的解决方案如下：

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-Ford 算法的基本思想，这里有一些来自 Wikipedia 的快速回顾：

the Bellman–Ford algorithm simply relaxes all the edges, and does this |V|-1 times, where |V| is the number of vertices in the graph.

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

Since the longest possible path without a cycle can be |V|-1 edges, the edges must be scanned |V|-1 times to ensure the shortest path has been found for all nodes.

A final scan of all the edges is performed and if any distance is updated, then a path of length |V| edges has been found which can only occur if at least one negative cycle exists in the graph.

Bellman-Ford 一开始假设距离非常大（无穷大），然后逐渐将它们降低到尽可能低的距离。这叫做放松。在每次迭代中，离源更远的边缘变得松弛。

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

现在假设你有一个没有负循环的图表。假设它有 10 个顶点，您需要不超过 9 次松弛即可到达（获得最短路径）距源最远的顶点。如果在 9 次放松后您仍然有所改善怎么办？您的图表中必须有负循环。

你代码中的ind是一个计数器。当ind == len(adj) - 1时表示你放宽了|V|次距离，说明存在负循环。

同时查看您自己的笔记中的倒数第三页。

负循环解释的 Bellman-ford 算法

Bellman-ford algorithm for negative cycles explanation

python

algorithm

bellman-ford