I have a directed graph that has all non-negative edges except the edge(s) that leave the source (S). There are no edges from any other vertices to the source. To find the shortest distance from source (S) to a vertex (T) in the graph, can I use Dijkstra's shortest path algorithm even though the edges leaving the source is negative?
0
votes
can you go from node S1 through negative edge to node S2 and then, through another negative edge back to S1? Or when you start, you cannot ever go back into start node S1?
- libik
Since there is no edge from any other vertices to the source I can't come back to source from any other node in the graph.
- Neel
That means, that edges from start node to other nodes have always direction, right?
- libik
Yes, it is a directed graph - sorry I forgot to mention.
- Neel
If this is the case have you considered remapping your edge weights to being positive? while I'm pretty sure you can use dijkstras for this case, it seems simpler to just map them all to positive numbers.
- Mike H-R
4 Answers
7
votes
Assuming only source-adjecent edges can have negative weights and there is no path back to the source from any of the source-adjecent nodes (as mentioned in the comment), you can just add a constant C onto all edges leaving the source to make them all non-negative. Then subtract C from the final result.
On a more general note, Dijkstra can be used to solve shortest-path in any graph with negative edge weights (but no negative cycles) after applying Johnson's reweighting algorithm (which is essentially Bellman-Ford, but needs to be performed only once).
2
votes
Yes, you can use Dijkstra on that type of directed graph.
If you use already finished alghoritm for Dijsktra and it cannot use negative values, it can be good practise to find the lowest negative edge and add that number to all starting edges, therefore there is no-negative number at all. You substract that number after finishing.
If you code it yourself (which is acutally pretty easy and I recommend it to you), you almost does not change anything, just start with lowest value (as usual for Dijkstra) and allow it, that lowest value can be negative. It will work in your case.
1
votes
The reason you generally can't use Dijkstra's algorithm for (directed) graphs with negative links is that Dijkstra's algorithm is greedy. It assumes that once you pick a vertex with minimum distance, there is no way it can later be reached by a smaller paths.
In your particular graph, after the very first step, you traverse all possible negative edges and Dijkstra's assumption actually holds from now on. Regardless of the fact that those vertices directly connected to start now have negative values, once you identify which has the minimum distance, it can never be reached again with a smaller distance (since all edges you would traverse from this point on would have a positive distance).
1
votes
If you think about the conditions that dijkstra's algorithm puts upon the edges for the algorithm to work it is only that they are never decreasing after initialisation.
Thus, it actually doesn't matter if the first step is negative as from those several points onwards the function is constantly increasing and thus the correct output will be found (provided there is no way to get back to the start square.).
