# finding all vertices on a negative cycle using belman ford twice

We are given that the following algorithm finds the vertices inside a negative cycle and we need to show an example for it such that it fails.

for each  v in V
dist[v] = inf+
dist[s] = 0
for i=1 to |V| - 1
for each (u,v) in E
relax(u,v,w)
for each v in V
dist'[v] = dist[v]
for i=1 to |V|
for each (u,v) in E
relax(u,v,w)
A = {v:dist[v] != dist'[v]}

relax(u, v, w):
if dist[v] > dist[u] + w(u, v):
dist[v] = dist[u] + w(u, v)
v.p = u



Can someone show me a graph with a negative cycle that will not bring the right result?

• What do you mean by "does not work"? What task do you want to solve?
– D.W.
Dec 20 '21 at 20:28
• What did you try? Where did you get stuck? Dec 20 '21 at 22:34