pythonpython-3.xalgorithmgraphbellman-ford

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


I am following this tutorial: Bellman-Ford Algorithm by Jessica Su and implemented the Algorithm 2 enter image description here

as follows:

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

The complete code is here.

The snippet failed the last test case where the graph is like this:

enter image description here

In that case, the update mechanism cannot guarantee that memorization_table[i] saved the smallest value since there are two paths and they are not compared.

Hence I wonder if the pseudo-code is wrong or my implementation is wrong?


Solution

  • The algorithm's pseudo code in the lecture notes has a mistake in this line:

          𝑑𝑘 ← min{𝑑𝑘−1[𝑣], 𝑑𝑘−1[𝑢] + 𝑤(𝑢,𝑣)} // update estimate of v

    This would make the value of 𝑑𝑘 only dependent on the last visited edge (𝑢,𝑣). The effect on 𝑑𝑘 of any previously visited edge to 𝑣 would be overwritten.

    Instead, this line should read:

          𝑑𝑘 ← min{𝑑𝑘[𝑣], 𝑑𝑘−1[𝑢] + 𝑤(𝑢,𝑣)} // update estimate of v

    This way the value of 𝑑𝑘 becomes the minimum of all 𝑑𝑘−1[𝑢] + 𝑤(𝑢,𝑣)