我对 Bellman-Ford 算法正确性的实现是错误的吗？

Question

我正在学习本教程：Bellman-Ford Algorithm by Jessica Su 并实现了算法 2

如下：

def negative_cycle(adj, cost):
    """
    detect negative cycle in a graph
    reference: https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf
    param adj: list of list, index represent nodes, and values the edges starting from them
    param cost: list of list, index represent nodes, and values the corresponding weights of edges
    return 0 or 1: 1 represents that there is at least 1 negative cycle in the graph
    >>> negative_cycle([[1], [2], [0], [0]], [[-5], [2], [1], [2]])
    1
    >>> negative_cycle([[1], [2], [3], [0]], [[2], [3], [1], [2]])
    0
    >>> negative_cycle([[1, 3], [2], [], [2]], [[3, 7], [4], [], [5]])
    0
    """
    vertex_num = len(adj)
    memorization_table = np.matrix(np.ones((vertex_num, vertex_num)) * np.inf)
    memorization_table[:, 0] = 0.0

    for i in range(1, vertex_num):
        for u in range(0, vertex_num):
            for j, v in enumerate(adj[u]):
                memorization_table[i, v] = min(memorization_table[i-1, v], memorization_table[i-1, u]+cost[u][j])

    for u in range(0, vertex_num):
        for j, v in enumerate(adj[u]):
            if memorization_table[i, v] > memorization_table[i-1, u]+cost[u][j]:
                return 1
    return 0

完整代码为here.

该代码段未通过最后一个测试用例，其中图形如下所示：

在这种情况下，更新机制不能保证memorization_table[i]保存最小的值，因为有两条路径并且它们没有被比较

所以我想知道是伪代码有误还是我的实现有误？

Answer 1

讲义中的算法伪代码这一行有错误：

← min{₋₁[], ₋₁[] + (, )} // 更新 v

的估计

这将使的值仅依赖于最后访问的边 (,)。任何先前访问过的边对的影响将被覆盖。

这一行应该改为：

← min{[], ₋₁[] + (,)} // 更新 v

的估计

这样的值就变成了所有₋₁[] + (,)

中的最小值

我对 Bellman-Ford 算法正确性的实现是错误的吗？

Is my implement of the correctness of Bellman-Ford algorithm wrong?

python

algorithm

graph

python-3.x

bellman-ford