There is a contradiction in the Johnson’s algorithm presented in CLRS edition 3 page 700 that I can't understand.

Johnson’s algorithm uses the technique of reweighting, which works as follows: for each edge $(u,v)$ that may has a negative weight, a new weight is assigned which is as follow:

Given a weighted, directed graph $G=(V,E)$ with weight function $w:E \rightarrow \mathbb R$, let $h:V \rightarrow \mathbb R$ be any function mapping vertices to real numbers. For each edge $(u, v) \in E$, define $\hat w(u,v) = w(u,v) + h(u) - h(v)$

The book in page 702 proves that $G$ has a negative-weight cycle using weight function $w$ if and only if $G$ has a negative-weight cycle using weight function $\hat w$.

On the other hand in page 702 it shows that for each $(u,v) \in E, \hat w(u,v) \geq 0$ .

Here is a my problem, how a negative-weight cycle of $G$ using $w$ weight function produces a negative-weight cycle using $\hat w$ weight function when it already has been proved that $\hat w(u,v) \geq 0$ for every edge $(u,v)$?

  • $\begingroup$ Is there no "precondition" saying that $\hat{w}(u,v) \geq 0$ is only true if $G$ has no negative-weight cycles? That would explain the contradiction. $\endgroup$ – user53923 May 31 '17 at 15:29
  • $\begingroup$ @user53923 no there is not. With out assuming any thing about negative-weight cycle it proves that no weight is negative. In fact this algorithm is trying to use Dijistra algorithm when some of the edges have negative weight. $\endgroup$ – M a m a D May 31 '17 at 15:31
  • 1
    $\begingroup$ Have you tried working through a simple example of a graph with a negative cycle? $\endgroup$ – D.W. May 31 '17 at 16:54
  • $\begingroup$ @D.W. actually no, But I think the proofs are enough. $\endgroup$ – M a m a D Jun 1 '17 at 4:12
  • 2
    $\begingroup$ @user53923 after reading the proof again, its proof is based on the condition that $G$ has no negative-weight cycle. $\endgroup$ – M a m a D Jun 1 '17 at 7:24

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.