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 edges.

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?