最長経路問題 NetworkX

最長経路問題

NetworkXを使って簡単な最長路問題を解いてみましょう。

[単純なグラフ]

まず、networkxをインストールして、次のようにインポートします。

1
import networkx as nx

次に、グラフを作成します。ここでは、有向グラフを作成します。

1
G = nx.DiGraph()

グラフにノードを追加します。

1
G.add_nodes_from([1, 2, 3, 4, 5])

ノード間のエッジを追加します。各エッジには、重みがあると仮定します。

1
G.add_weighted_edges_from([(1, 2, 3), (1, 3, 4), (2, 3, 1), (2, 4, 6), (3, 4, 2), (3, 5, 7), (4, 5, 8)])

これでグラフが完成しました。

最長経路問題を解くには、NetworkXのlongest_path関数を使用します。

1
2
longest_path = nx.dag_longest_path(G)
print(longest_path)

これで、最長経路が求められます。

最長経路の出力は、最初のノードから最後のノードまでの最長経路上のノードのリストです。

注意：

この方法は、有向非巡回グラフ（DAG）にのみ適用されます。

循環がある場合は、longest_path関数はエラーを返します。

全ソースコードと結果

上記のコードをまとめると以下のようになります。

[全ソースコード]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import networkx as nx

# ①グラフの作成
G = nx.DiGraph()

# ②ノードの追加
G.add_nodes_from([1, 2, 3, 4, 5])

# ③エッジの追加
G.add_weighted_edges_from([(1, 2, 3), (1, 3, 4), (2, 3, 1), (2, 4, 6), (3, 4, 2), (3, 5, 7), (4, 5, 8)])

# ④最長経路の計算
longest_path = nx.dag_longest_path(G)

# ⑤結果の出力
print("最長経路: ", longest_path)

実行結果は次の通りです

[実行結果]

最長経路:  [1, 2, 4, 5]

1 ⇒ 2 ⇒ 4 ⇒ 5という最長経路を求めることができました