java - 确定JUNG图中的两个节点是否通过多条路径连接的快速方法？

Question

给定两个节点A并B从有向 JUNG 图中，我想确定是否有多个路径 from Ato B（不一定是最短路径）。

我只能想到两种方法，都非常耗时。

1. 检索连接两个节点的所有路径（问题正在查找 JUNG 中的所有路径？）并检查是否有多个。

2. 使用 class 检索最短路径 DijkstraShortestPath，然后断开此路径并再次搜索最短路径。如果还有一个，则意味着有多个路径。请注意，这也需要克隆图形，因为我不想更改原始图形。

我怎样才能更聪明地做到这一点（即更快）？

Answer 1

我自己找到了解决方案。

我的问题有一个额外的限制，我只想检查是否有多个路径仅用于与和 edge 直接连接的两个节点。这意味着通过简单地计算最短路径，您将始终将这条单边作为路径。

所以，我的问题可以重新表述为：

除了边缘本身之外，是否有另一条路径连接边缘的两个节点？

解决方案是使用加权最短路径。如果我们为感兴趣的边缘分配非常高的权重，并1为所有其他边缘分配权重，那么如果最小距离低于我们的高权重，则答案为YES，否则为NO。

这是代码：

public static boolean areThereMultiplePaths(final Edge edge, DirectedGraph<Entity, Edge> graph) {
        Transformer<Edge, Integer> transformer = new Transformer<Edge, Integer>() {
            public Integer transform(Edge otherEdge) {
                if (otherEdge.equals(edge))
                    return Integer.MAX_VALUE;
                else
                    return 1;
            }
        };

        DijkstraShortestPath<Entity, Edge> algorithm = new DijkstraShortestPath<Entity, Edge>(graph, transformer);
        Double distance = (Double) algorithm.getDistance(edge.getStartNode(), edge.getEndNode());

        return distance < Integer.MAX_VALUE; 
    }