4

networkx では、

shortest_path(G, source=None, target=None, weight=None)  
# weight/distance/cost 1 by default

グラフ内の 2 つのノード間の最短経路を計算するための演算子としてエッジ プロパティ「重み」をサポートできます。

ただし、ノード/エッジにアタッチされた他のメタクラスがある場合、たとえば:

class meta( object ):
    def __init__( self, weight_shift = 1 ):
        self.weight_shift = weight_shift

G.add_node('A', meta_data = meta( weight_shift = 100 ) )
G.add_node('B', meta_data = meta( weight_shift = 200 ) )
G.add_node('C')
...
G.add_edge("A", "C", weight=10, meta_data = meta( weight_shift = -5 ))  
G.add_edge("B", "C", weight=10, meta_data = meta( weight_shift = -10 ))
G.add_edge("A","B")

shortest_path() の重みパラメータとして関数を定義することは可能ですか?

def weight_sum():
    ...

たとえば、ロジックを使用して、「実行時」の「重み」を計算できます。

weight_sum = edge.weight + edge.meta.weight_shift + node_left.meta.weight_shift + node_right.meta.weight_shift

それから

shortest_path(G, source="A", target="B", weight=weight_sum())

最短経路を取得するには？

ありがとう。

4

1 に答える 1

1

NetworkX の現在の実装では不可能です。

次の 2 つのオプションがあります。

1) 最短経路検索の前に、すべてのエッジを処理して、重み関数に従って新しいエッジ属性を追加します。その属性を shortest_path() の「重み」引数として使用します

2）次のように行を置き換えます

vw_dist = dist[v] + edgedata.get(weight,1)

ダイクストラのアルゴリズムのコードで、「重み」属性を取得する代わりに、エッジの重みにカスタム関数を使用します。

于 2012-09-18T02:22:11.570 に答える