networkxマルチパスのpython

Question

私は（OSPFがないように）イコールコストマルチパスをシミュレートしようとして与えられたグラフ内のすべての最短パスを取得するにはnetworkxライブラリを使用してい

：

は

ので、たとえば、私が取得したいと思います（次の与えられましたグラフ）：

H.add_edge('R1','R2',weight=5)

H.add_edge('R1','R3',weight=5)

H.add_edge('R4','R2',weight=5)

H.add_edge('R4','R3',weight=5)

この出力：行うことが可能である

[['R1', 'R2', 'R4'], ['R1', 'R3', 'R4']] 

：私は10にエッジR4-R3で重量を変更した場合 [p for p in nx.all_shortest_paths(H,source='R1',target='R4')]

しかし、all_shortest_paths関数は、すべてのパスを示したままです。私の質問です：すべての最短経路を表示する機能や重量に応じて最短経路だけですか？

よろしくお願いいたします。

Answer 1

weiとして使用する複数の異なる属性を割り当てることができますghts、all_shortest_pathsは、使用したいラベルがわかりません。つまり、デフォルトでは、エッジの数を調べ、作成したウェイトを無視します。それはあなたが体重を提供することを可能にするオプションの引数を持っています。 documentationをご覧ください。それはall_shortest_paths(G, source, target, weight=None)によって呼び出されます。だからあなたは体重を定義する必要があります。あなたのケースでは

：

[p for p in nx.all_shortest_paths(H,source='R1',target='R4', weight = 'weight')] 

が希望の出力を提供します。

Answer 2

all_shortest_paths機能は重量を考慮しません。ただし、この場合、最短パスのエッジの重みを合計し、最大値を選択することで、目的の結果を得ることができます。

グラフを初期化：

import networkx as nx 

G = nx.Graph() 
G.add_weighted_edges_from([('R1', 'R2', 5), ('R1', 'R3', 5), ('R4', 'R2', 5), ('R4', 'R3', 10)]) 

shortest_paths = np.array(list(nx.all_shortest_paths(G, source='R1', target='R4'))) 

リストの理解を使用してパス内の各エッジの重みを計算する：

path_weights = np.array([sum([G.get_edge_data(path[edge], path[edge + 1])['weight'] for edge in range(len(path) - 1)]) for path in shortest_paths]) 

、最大総重量とshortest_pathsからパス（複数可）を選択します。

shortest_paths[path_weights == path_weights.max()]