java - 如何在JGraphT中的图形上允许负权重？

我有一个图，想要找到从源到接收器的最长路径。
我的想法是将权重反转为负数，然后在其上运行dijkstra，如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());
        }
    }

不幸的是，当我想设置负重量时，出现错误“不允许负重量”。

最佳答案

我们不允许负权重的原因是因为不可能在负负周期的图中找到最短路径。负循环是指总重量（其边缘的权重之和）为负的循环。

通常，在任意图中找到最长路径是NP难的，请参见例如https://en.wikipedia.org/wiki/Longest_path_problem

如果您的图是有向无环图（DAG），则可以找到线性时间中最长的路径。

因此，总而言之，这实际上不是JGraphT问题，而是与您要解决的问题的复杂性有关的问题。