-1
$\begingroup$

I'm exploring the Bellman-Ford algorithm to detect and track negative cycles (a collection of ncycle that we can see in the implementation). I'm wondering if the algorithm finds the same collection regardless of the source node when we can reach any node from any other node.

$\endgroup$
9
  • 2
    $\begingroup$ What do you mean by the "set" of negative cycles that Bellman-Ford finds? I suggest you edit your question to make it more precise. There might be a ton of negative cycles, and any particular execution of Bellman-Ford might reveal only one of those cycles. $\endgroup$
    – D.W.
    Commented Apr 30 at 7:19
  • $\begingroup$ @D.W. I added the algorithm I refer to. $\endgroup$
    – atos
    Commented Apr 30 at 7:46
  • 2
    $\begingroup$ I know what the Bellman-Ford algorithm is. That doesn't help. What is the motivation for this question? In what context did you encounter it? I don't understand what you mean by "a collection of ncycle" - perhaps you are referring to a specific implementation, but some context seems to be missing. $\endgroup$
    – D.W.
    Commented Apr 30 at 7:47
  • $\begingroup$ Have you checked the link? It describes said implementation (along with ncycle we get for every edge). $\endgroup$
    – atos
    Commented Apr 30 at 9:25
  • 1
    $\begingroup$ I believe there might be some confusion here. ncycle is simply a linked list (presumably, or any ordered set of elements) that contains all vertices of some negative-weight cycle in the graph (i.e. a cycle where the sum of all weights is below $0$). It is not the set of all negative-weight cycles in the graph. $\endgroup$ Commented Apr 30 at 10:54

1 Answer 1

3
$\begingroup$

Your question is unclear since it is not explicit what a "collection of ncycle" means. I believe you are asking whether the Wikipedia implementation of the Bellman-Ford algorithm finds the same negative-weight cycle (assuming there is one) regardless of which source vertex we pick in the final depth-first search (DFS) when the input graph is strongly connected (i.e. for any pair of vertices $u,v$, there exist directed paths from $u$ to $v$ and $v$ to $u$).

The answer is "no." Consider the following graph.

enter image description here

As you can observe, it is strongly connected; you can pick any pair of distinct vertices $u,v$ and find a path from $u$ to $v$. Yet, picking vertex 1 as a source for the final negative-weight cycle detection yields the cycle 1, 2, 3, while picking vertex 4 as a source yields 4, 5, 6.

$\endgroup$
2
  • $\begingroup$ Will the answer change if we have a complete digraph? $\endgroup$
    – atos
    Commented Apr 30 at 12:30
  • $\begingroup$ No, it will not. Even in the case of a complete digraph, multiple disjoint negative-weight cycles are possible. $\endgroup$ Commented May 1 at 8:37

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.