CODEWITHSUNDEEP
javagraphdijkstrajgraphtlongest-path
Flontis
Flontis

Reputation: 347

How to allow negative weights on a Graph in JGraphT?

I have a graph and want to find the LONGEST path from source to sink. My idea was to reverse the weight to negative numbers and run dijkstra on it, as implemented in JGraphT

ListenableDirectedWeightedGraph<String, MyEdge> g = new ListenableDirectedWeightedGraph<String, MyEdge>(
                MyEdge.class);

...

List<MyEdge> sp = DijkstraShortestPath.findPathBetween(g, "source", "sink");

public static class MyEdge extends DefaultWeightedEdge {

        @Override
        public String toString() {
            return String.valueOf(getWeight());
        }
    }

Unfortunately, i'm getting the error "negative weights not allowed" when i want to set a negative weight.

Upvotes: 0

Views: 247

Answers (2)

Flontis
Flontis

Reputation: 347

Answer by c0der: Consider "re scaling" the weights. Make the lowest negative value 0 and add the same value to all weights.

Nice idea, works of cause.

Upvotes: 0

Joris Kinable
Joris Kinable

Reputation: 2411

The reason we don't allow negative weights is because finding a shortest path in a graph with negative weight cycles is impossible. A negative cycle is a cycle whose total weight (sum of the weights of its edges) is negative.

In general, finding the longest path in an arbitrary graph is NP-hard, see e.g. https://en.wikipedia.org/wiki/Longest_path_problem

If your graph is a directed acyclic graph (DAG), you can find the longest path in linear time.

So in summary, this is not really a JGraphT issue, but an issue with the complexity of the problem you want to solve.

Upvotes: 0

Related Questions