What modifications could you make to a graph to allow Dijkstra's algorithm to work on it?

Question

So I've been thinking, without resorting to another algorithm, what modifications could you make to a graph to allow Dijkstra's algorithm to work on it, and still get the correct answer at the end of the day? If it's even possible at all?

I first thought of adding a constant equal to the most negative weight to all weights, but I found that that will mess up everthing and change the original single source path.

Then, I thought of traversing through the graph, putting all weights that are less than zero into an array or somwthing of the sort and then multiplying it by -1. I think his would work (disregarding running time constraints) but maybe I'm looking at the wrong way.

EDIT: Another idea. How about permanently setting all negative weights to infinity. that way ensuring that they are ignored?

So I just want to hear some opinions on this; what do you guys think?

Answer 1

Seems you looking for something similar to Johnson's algorithm:

1. First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.

2. Second, the Bellman–Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.

3. Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) − h(v).

4. Finally, q is removed, and Dijkstra's algorithm is used to find the shortest paths from each node s to every other vertex in the reweighted graph.

By any algorithm, you should check for negative cycles, and if there isn't negative cycle, find the shortest path.

In your case you need to run Dijkstra's algorithm one time. Also note that in Johnson's algorithm semi Bellman–Ford algorithm runs just for new added node. (not all vertices).