2

2つのノードを接続し、同じノードを2回使用しないグラフでパスを見つけたい。エッジの重みの合計は、特定の範囲内にある必要があります。

これをpygraphに実装する必要があります。この目的で使用できるアルゴリズムがすでにあるかどうかはわかりません。これを達成するための最良の方法は何ですか？

4

1 に答える 1

2

編集： 私は最初に質問を誤解しました。答えを訂正しました。この機能はライブラリに組み込まれていませpygraphlibんが、簡単に実装できます。基本的に最短経路を取得し、事前定義された範囲内にあるかどうかを判断し、重みが最小のエッジを削除して、新しい最短経路を計算し、繰り返すこのようなものを考えてみます。

from pygraphlib import pygraph, algo

edges = [(1,2),(2,3),(3,4),(4,6),(6,7),(3,5),(4,5),(7,1),(2,5),(5,7)]
graph = pygraph.from_list(edges)

pathList = []
shortestPath = algo.shortest_path(graph, startNode, endNode)
cost = shortestPath[len(shortestPath)-1][1]

while cost <= maxCost:
    if cost >= minCost:
        pathList.append(shortestPath)

    minEdgeWt = float('inf')
    for i in range(len(shortestPath)-1):
        if shortestPath[i+1][1] - shortestPath[i][1] < minEdgeWt:
            minEdgeWt = shortestPath[i+1][1] - shortestPath[i][1]
            edgeNodes = (shortestPath[i][0], shortestPath[i+1][0])

    #Not sure of the syntax here, edgeNodes is a tuple, and hide_edge requires an edge.
    graph.hide_edge(edgeNodes)
    shortestPath = alog.shortest_path(graph, startNode, endNode)
    cost = shortestPath[len(shortestPath)-1][1]

return pathList

のコピーが見つからなかったことに注意してくださいpygraphlib。これは開発中ではないため、上記のコードをテストできませんでした。それは機能するはずです、構文の不確実性を修正します。また、可能であれば、 Pythonでのあらゆる種類のグラフ操作にnetworkx[ link ]を使用することをお勧めします。これは、より完全で、活発な開発が行われており、より完全に文書化されているためですpygraphlib。ただの提案。

于 2011-10-11T15:45:37.987 に答える