3

これを行うにはどうすればよいですか？これは宿題で、私はそれで大きな問題を抱えています。さて、問題は、ライブラリを使用してはならないということです。

次のようなグラフがあります。

{'A': {'C': 2, 'B': 10}, 'C': {'B': 7, 'D': 2}, 'B': {}, 'D': {'A': 5, 'B': 4}}

ファイルから取得した辞書を使用します。

http://www.python.org/doc/essays/graphs/のアルゴリズムを使用してすべてのパスを見つけているので、問題はありません。

しかし、あるポイントから別のポイントへのすべてのパスを取得したので、重みを合計して、その完全なコストを取得する必要があります。

あなたが私を助けて、それに近づくための良い方法を教えてくれたら、私はそれを感謝します.

4

3 に答える 3

2

これnetworkxは非常に優れた Python グラフ ライブラリです。そのドキュメントを読むと、簡単な解決策があることがわかります。これは宿題なので、コーディングの問題が見つかるまでこれ以上コメントしません。

于 2012-06-28T15:10:28.763 に答える
1 
gr = {'A': {'C': 2, 'B': 10},
      'C': {'B': 7, 'D': 2},
      'B': {'E': 2},
      'D': {'A': 5, 'B': 4, 'E': 3}
      'E': {}}

def paths(gr, frm, to, path_len=0, visited=None):

    if frm == to:
        return [[to, path_len]]

    visited = visited or []
    result = []
    for point, length in gr[frm].iteritems():
        if point in visited:
            continue
        visited.append(point)
        for sub_path in paths(gr, point, to, path_len + length, visited[:]):
            result.append([frm] + sub_path)

    return result

>>> print paths(gr, 'A', 'E')
[['A', 'C', 'B', 'E', 11], ['A', 'C', 'D', 'E', 7], ['A', 'B', 'E', 12]]
于 2012-06-28T16:03:08.350 に答える
0

さて、あなたは道を見つけるの難しい部分をしました。ここで、パスを通過して、それらの重みを合計します。ループを使用します。

int sum=0;
for(int i=0;i<path.size()-1;i++)
    sum+= node.at(i).getWeightFor(node.at(i+1))

getWeightFor(node)そのノードから別のノードに移動するためのコストをどこに返すか。したがって、そうするとA.getWeightFor(C)、2が返されます。おそらくもっと良い方法がありますが、それが私の簡単な答えです。そのgetWeightFor関数を作成する必要がありますが、それは非常に単純なはずです。私が言ったように、難しい部分は行われます。この最後のビットを考えすぎないでください。

于 2012-06-28T14:52:47.137 に答える