0
$\begingroup$

I am going through Warshall and Floyd algorithms and I read that Floyd's algorithm does not hold if a graph has negative circle. I have not been able to fully figure out what negative circle means. Therefore, I would like to know more about positive and negative circles.

$\endgroup$
3
$\begingroup$

A circle is a path in the graph ($v\to u_1 \to u_2 \to \cdots \to v$) starting from some node $v$, that goes back to node $v$, thus "closing a circle".

The "value" of a circle, is the sum of the weights of the edges in the circle. If they sum to a negative value -- the circle is "negative"; otherwise, it is "positive".

$\endgroup$
  • $\begingroup$ I should have figured this out by myself, poor soul. $\endgroup$ – user618677 Apr 22 '16 at 22:40
  • $\begingroup$ So, if I do currency trading(moving from one to the other and finally to the start currency) a positive circle means that I will make money. It that correct? $\endgroup$ – user618677 Apr 22 '16 at 22:43
  • 1
    $\begingroup$ @user618677, please don't use the comments to ask new questions. This is a question-and-answer site, not a discussion forum, and on this site, comments exist mainly to help people improve their questions/answers. If you have a follow-on question and you've put a substantial amount of effort into it, you can ask a new question (but fair warning: that particular question might not be well-received, because I suspect if you work through a few examples you'll be able to work out the answer on your own). Thank you! $\endgroup$ – D.W. Apr 23 '16 at 4:17
  • $\begingroup$ DW, no need of trying to be polite here. I am just trying to internalizing some basic concepts and build up my own understanding. $\endgroup$ – user618677 Apr 23 '16 at 19:28

Your Answer

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

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