javagraphdijkstrajgraphtlongest-path

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.

Solution

  • 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.