CODEWITHSUNDEEP
algorithmshortest-pathdijkstradirected-acyclic-graphstopological-sort
Bal
Bal

Reputation: 13

Dijkstra’s algorithm - DAG Shortest path with ONLY negative costs

I am looking for the shortest path between source (s) and sink (t) in an acyclic directed graph. The graph has topological order (temporal). All the edges have or negative or null cost. Is it still possible to use Dijkstra algorithm? The graph looks like this: graph example

Usually Dijkstra does not work with negative weights since the nodes are explored only once (with the assumption that the cost can only increase). In this case, since I have only negative (or null cost), and the cost can only decrease, is ensured that the path is optimal if I explore the graph following the topological order?

Thank you

Upvotes: 1

Views: 1369

Answers (2)

amit
amit

Reputation: 178521

Yes, it will be optimal - but that's not Dijkstra's algorithm.

Dijkstra's algorithm specifies how to explore the nodes - according to their current weight. From the original article:

The shortest branch of set II is removed from this set and added to set I. As a result one node is transferred from set B to set I .

What you are describing is a different solution, and it works:

D[source] = 0
D[v] = min {D[u] + w(u,v) | u in V}

Now, since you are following topological order, you can prove by induction the above formula is correct - since assuming the induction hypothesis is correct for all u that is explored before v, the conclusion that D[v] is also correct (since it won't be reopened) holds.

P.S. This proof does not even require the assumption of only negative weights, it works well if the weights are mixed, so the same solution holds.

Upvotes: 2

Damien Prot
Damien Prot

Reputation: 593

What you are looking at is hence a longest path on a graph with positive weights (you just have to take the opposite of each value). This problem is in fact NP-hard for general graphs, but it becomes solvable in linear time if the graph is a Directed Acyclic Graph. A very good explanation is given here for example.

Upvotes: 0

Related Questions