如何在 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());
        }
    }

不幸的是，当我想设置负权重时出现错误 "negative weights not allowed"。

Answer 1

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

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

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

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

Answer 2

c0der的回答：考虑 "re scaling" 权重。将最小的负值设为0，所有权重加相同的值。

好主意，事业有成。

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

How to allow negative weights on a Graph in JGraphT?

java

graph

dijkstra

jgrapht

longest-path