# Solving shortest path problem with Dijkstra’s algorithm for n negative-weight edges and no negative-weight cycle

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?

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