2
$\begingroup$

Given directed graph $G=(V,E,\omega,s,t)$ that $\omega:E\to \mathbb{R}$ is the weight function on $E$, and we want to find shortest path from $s$ to $t$. First, we run the Bellman-Ford algorithm to finding the shortest path from $s$ to $t$, but after the termination of the algorithm, I know that if the distance of a node $v$ changed, then the graph contains a negative cycle that reachable from the source, so, can we conclude that $v$ necessarily appear in a negative cycle or not?

My attempt: I think not necessarily $v$ appears in a negative cycle. Consider the below example that $t$ not on any negative cycle, but after the termination of the algorithm, if we update the distance, its distance changed. Can we conclude that $v$ sometimes appears in a negative cycle or sometimes not appear on any cycle?

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

You are right. It doesn't mean that it will appear in a negative cycle. Rather, it means that there exists some negative cycle $C$ that is reachable from the source node $s$ and $v$ can be reached from $C$.

Since the distance for any node inside a negative cycle is practically negative infinity (for any negative value, after a certain number of iterations the distance will be smaller than that), then the distance for any node that can be reached from it is also negative infinity. Meaning that this is not a good way to detect which edges are in the negative cycle.

If you want to find the negative cycle, you can actually do something easy:

  1. Run bellman ford
  2. Do an extra iteration of bellman ford. If nothibg changed, there is no negative cycle. Otherwise, there is.
  3. If there is a negative cycle, let $w$ be a node that changed in step 2
  4. Do $w\leftarrow parent(w)$ at least $|V|$ times.
  5. This resulting $w$ (after you did step 4), and all other nodes that you get by doing $w\leftarrow parent(w)$ (again, only after step 4. In step 4 the nodes you see don't count), have to be the negative cycle.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.