0

2 つのノードが与えられ、有向 JUNG グラフからA、からへのパス(必ずしも最短Bパスである必要はありません)が複数あるかどうかを判断したいと考えています。AB

2 つの方法しか考えられませんが、どちらも非常に時間がかかります。

  1. 2 つのノードを接続するすべてのパスを取得し (質問JUNG ですべてのパスを検索しますか? )、複数存在するかどうかを確認します。

  2. class を使用して最短パスを取得し、 DijkstraShortestPathこのパスを切断して再度最短パスを検索します。まだ 1 つある場合は、複数のパスがあったことを意味します。元のグラフを変更したくないため、これにはグラフのクローンも必要であることに注意してください。

これをよりスマートに（つまり、より速く）行うにはどうすればよいですか？

4

1 に答える 1

0

私は自分で解決策を見つけました。

私の問題には、直接接続されている 2 つのノードと edge に対してのみ複数のパスがあるかどうかのみを確認したいという追加の制約があります。これは、最短パスを計算するだけで、常にこの単一のエッジをパスとして取得できることを意味します。

したがって、私の質問は次のように再定式化できます。

エッジ自体以外に、エッジの 2 つのノードを接続する別のパスはありますか?

解決策は、加重最短パスを使用することです。関心のあるエッジに非常に高い重みを割り当て、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; 
    }
于 2013-04-19T13:44:36.213 に答える