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

Question

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

不幸的是，当我想要设置负权重时，我得到了错误“不允许负权重”

Answer 1

答案是： 考虑“重新缩放”权重。将最小负值设为0，并将相同的值添加到所有权重

好主意，事出有因

Answer 2

我们不允许负权重的原因是，在具有负权重循环的图中寻找最短路径是不可能的。负循环是指总权重（其边的权重之和）为负的循环

一般来说，在任意图中寻找最长路径是NP困难的，参见例https://en.wikipedia.org/wiki/Longest_path_problem

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

总之，这不是一个JGraphT问题，而是一个你想要解决的问题的复杂性问题