# I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs [duplicate]

1. Add a constant $$c\geq |w_{min}|$$ to each edge of $$G$$, so that each edge now has non-negative weight.
2. Run Dijkstra's algorithm

Can anyone tell me if this is viable or if it fails?

Let $$G(V, E)$$ denote a graph with a cost function $$c:e\in E\mapsto Z$$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $$e\langle v_i, v_j\rangle$$ with a negative cost, i.e., $$c(e_{ij}) <0$$, so that $$w_{min}=c(e_{ij})$$.
Let $$G'(V, E)$$ denote a graph where the cost of each edge is now $$c'(e_{ij})=c(e_{ij}) + w_{min}, \forall v_i, v_j\in V$$. Certainly, there are no negative edge costs in $$G'$$.
Running Dijkstra on $$G'$$ to find the shortest path between two arbitrary vertices $$s$$ and $$t$$ would return a path $$\pi:\langle s=v_0, v_1, v_2, ..., v_n=t\rangle$$ with a cost equal to $$\sum_{i=0}^{n-1}c'(e_{i, i+1})=\sum_{i=0}^{n-1}\left(c(e_{i,i+1})+w_{min}\right)=n\times w_{min}+\left(\sum_{i=0}^{n-1}c(e_{i, i+1})\right)$$ ---please note the usage of $$c'$$ and $$c$$ in these expressions. In other words, the overall cost of paths in $$G'$$ penalizes larger paths by the constant $$w_{min}$$ and in the end, it might very easily return a different path.
It does not matter whether you correct now the cost of the path returned by running Dijkstra in $$G'$$, as it might be simply different.