I am following this tutorial: Bellman-Ford Algorithm by Jessica Su and implemented the Algorithm 2
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:
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?
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[𝑢] + 𝑤(𝑢,𝑣)