0
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.