9

networkxを使用してグラフを操作しています。私はかなり大きなグラフ（200ノード近く）を持っており、2つのノード間のすべての可能なパスを見つけようとしています。しかし、私が理解しているように、networkxは最短経路しか見つけることができません。最短経路だけでなく、すべての可能な経路を取得するにはどうすればよいですか？

UPD：パスには各ノードを1回だけ含めることができます。

UPD2：ここで説明されているfind_all_paths（）関数のようなものが必要です：python.org/doc/essays/graphs.htmlしかし、この関数は多数のノードとエッジ付き=（

4

3 に答える 3

13

Python用の別のグラフモジュールであるigraphは、ノードの特定のペア間のすべての最短経路を計算できます。このようなパスは無限にあるため、すべてのパスを計算しても意味がありません。

頂点0からのすべての最短経路を計算する例：

>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]

igraph 0.6以降（これは執筆時点での開発バージョンです）を使用している場合は、結果をget_all_shortest_paths特定の終了頂点に制限することもできます。

>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
 [0, 1, 2, 12, 13, 14, 15],
 [0, 10, 11, 12, 13, 14, 15],
 [0, 1, 11, 12, 13, 14, 15],
 [0, 1, 2, 3, 13, 14, 15],
 [0, 1, 2, 3, 4, 5, 15]]

もちろん、注意する必要があります。たとえば、100 x 100のグリッドグラフ（Graph.Lattice([100, 100], circular=False)igraphで簡単に生成できる）があるとします。左上のノードから右下のノードにつながる最短経路の数は、200から100の要素を選択する可能性の数に等しくなります（証明：そこにある最短経路の長さには200のエッジがあり、そのうち100は「水平」になりますグリッド内にあり、そのうち100個は「垂直方向」に移動します）。これはおそらくあなたの記憶に収まらないので、これら2つのノード間のすべての最短経路を計算することさえここでは実際には実行可能ではありません。

2つのノード間のすべてのパスが本当に必要な場合は、igraphを使用して、前述のWebページに記載されている関数を書き直すことができます。これは、igraphのコアがCで実装されているため、純粋なPythonソリューションよりも高速です。

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in set(graph.neighbors(start)) - set(path):
        paths.extend(find_all_paths(graph, node, end, path))
    return paths

グラフを最初に隣接リスト表現に変換することで、より最適化できます。これは、次の呼び出しを繰り返す必要がないためgraph.neighborsです。

def find_all_paths(graph, start, end):
    def find_all_paths_aux(adjlist, start, end, path):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path))
        return paths

    adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
    return find_all_paths_aux(adjlist, start, end, [])

編集：igraph 0.6だけでなく、igraph0.5.3でも機能するように最初の例を修正しました。

于 2010-04-09T10:34:06.583 に答える
11

これは実際にはnetworkxで機能し、再帰的ではないため、大きなグラフに適している場合があります。

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths
于 2011-04-16T00:05:14.937 に答える
0

ダイクストラのアルゴリズムは、幅優先探索と同様の方法で最短経路を見つけます（BFSのナイーブキューの代わりに、グラフの深さで重み付けされた優先キューを置き換えます）。いくつかの選択肢が必要な場合は、かなり簡単に拡張して「N」最短パスを生成できますが、パスを大幅に異なるものにする必要がある場合（たとえば、セキュリティバンのルートをスケジュールする場合）、選択についてより賢くする必要があります。互いに大幅に異なるパス。

于 2010-04-09T09:00:14.790 に答える