CODEWITHSUNDEEP
graphshortest-path
Janathan
Janathan

Reputation: 63

Shortest acyclic path on directed cyclic graph with negative weights/cycles

I have a directed graph which has cycles. All edges are weighted, and the weights can be negative. There can be negative cycles.

I want to find a path from s to t, which minimizes the total weight on the path. Sure, it can go to negative infinity when negative cycles exist. But what if I disallow cycles in the path (not in the original graph)? That is, once the path leaves a node, it can not enter the node again.

This surely avoids the negative infinity problem, but surprisingly no known algorithm is found by a search on Google. The closest is Floyd–Warshall algorithm, but it does not allow negative cycles.

Thanks a lot in advance.

Edit: I may have generalized my original problem too much. Indeed, I am given a cyclic directed graph with nonnegative edge weights. But in addition, each node has a positive reward too. I want to find a simple path which minimizes (sum of edge weights on the path) - (sum of node rewards covered by the path). This can be surely converted to the question that I posted, but some structure is lost. And some hint from submodular analysis suggests this motivating problem is not NP-hard. Thanks a lot

Upvotes: 2

Views: 1965

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

I will copy my answer from this question on the CS-theory Stackexchange:

Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.

Upvotes: 2

Related Questions