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 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?