Shortest acyclic path on directed cyclic graph with negative weights/cycles
- by Janathan
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
