0

2 つのノード間ではなく、各ノードに重みがあるグラフを考えてみましょう。したがって、ノードに移動するコストは、そのノードの重みになります。

1- このグラフをどのように表すことができますか?

2- このタイプのグラフに最小スパニング パス アルゴリズムはありますか (または、既存のアルゴリズムを変更できますか)?

たとえば、行列を考えてみましょう。ある数から別の数に移動するとき、最小の合計を生成するパスはどれですか? (グラフは向きを合わせなければならないことに注意してください)

4

1 に答える 1

0

  1. 既存のアルゴリズムを調整してエッジ指向のアプローチを使用したくない場合は、ノードの重みをエッジの重みに変換できます。ノードvのすべての入力エッジについて、vの重みをエッジに保存します。それが表現です。

  2. さて、1のアプローチで、これはMSTのようなよく知られたアルゴリズムで簡単に実行できるようになりました。

必要に応じてグラフを表現し、ノードで重みを保持することもできます。アルゴリズムは単純に使用しませんでしたが、単純に実行されたWeight w = edge.weight();ものを使用しますWeight w = edge.target().weight() 。大きな調整は必要ありません。

隣接行列を使用する必要がある場合は、ノードの重みを持つ2番目の配列が必要であり、隣接行列では、エッジがない場合は0、エッジの場合は1-です。

それが役に立ったことを願っています

于 2012-09-18T07:56:19.110 に答える