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

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

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

如果您的图是有向无环图 (DAG)，您可以在线性时间内找到最长的路径。

所以总而言之，这并不是一个真正的 JGraphT 问题，而是一个你要解决的问题的复杂性问题。

Answer 2

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

好主意，事业有成。