1
$\begingroup$

Why are we interested in negative edge weight cycles when finding out SSSP. In a path, we are not allowed to traverse a node more than once.

$\endgroup$
2
$\begingroup$

In a simple path, no node can be traversed more than once. However, paths in general can. The SSSP asks for single-source shortest paths, without specifying that the paths need to be simple. This allows the paths to contain cycles. Thus, negative cycles are a concern as they may allow arbitrarily "short" paths, and so the definition of a "shortest" path falls apart. This is because if a path contains a node on a negative cycle, we can always lower the cost of the path by going around the negative cycle.

Of course, this also depends on how you define a path, and how the SSSP has been presented to you. The above explanation assumes typical definitions of both, so if you have different definitions, please leave a comment.

$\endgroup$

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.