Although many texts state Dijkstra's algorithm does not work for negative-weight edges, the modification of Dijkstra's algorithm can. Here is the algorithm to solve a single negative-weight edge without negative-weight cycle.

Let $d_s(v)$ be the shortest distance from source vertex s to vertex v.
Suppose the negative edge $e$ is $(u, v)$
First, remove the negative edge $e$, and run Dijkstra from the source vertex s.
Then, check if $d_s(u) + w(u, v) \leq d_s(v)$. If not, we are done. If yes, then run Dijkstra from $v$, with the negative edge still removed.
Then, $\forall t \in V $, $d(t) = min(d_s(t), d_s(u) + w(u, v) + d_v(t))$

Given the above algorithm, I want to modify the above algorithm again to solve n negative-weight edges and no negative weight cycle. Any hint?

  • 1
    $\begingroup$ You write: "... a single negative-weight edge without negative-weight edges." did you mean "without negative-weight cycles" ? $\endgroup$ – JimN Sep 8 '20 at 5:08
  • $\begingroup$ @JimN Yes, I mean without negative-weight cycles $\endgroup$ – hck007 Sep 8 '20 at 19:35

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.