全点対最短経路問題（NetworkX）

全点対最短経路問題

全点対最短経路問題（All-Pairs Shortest Path Problem）は、グラフ理論の基本的な問題の一つで、ある重みつきグラフにおいて、すべての頂点の間の最短経路を求める問題です。

具体的には、グラフの任意の2つの頂点u, vに対して、uからvへの最短経路の重みを求めます。

この問題は、ワーシャル-フロイド法やダイクストラ法などのアルゴリズムを使用して解決できます。

全点対最短経路問題は、多くの実世界の問題に適用されます。

例えば、都市間の移動にかかる最小コストを求める問題や、ネットワークの最小距離を求める問題などがあります。

また、グラフが静的である場合には、問題の解決に多項式時間がかかりますが、グラフが動的である場合には、解決が困難であることが知られています。

例題

すべての頂点のペアの最短経路を求めてみます。

NetworkXは、ワーシャル-フロイド法を実装した関数 shortest_pathを提供しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import networkx as nx

# 無向グラフの定義
G = nx.Graph()

# 頂点の追加
G.add_nodes_from([1, 2, 3, 4, 5])

# 辺の追加
G.add_edge(1, 2, weight=5)
G.add_edge(1, 3, weight=2)
G.add_edge(1, 4, weight=6)
G.add_edge(2, 3, weight=3)
G.add_edge(2, 4, weight=2)
G.add_edge(3, 4, weight=1)
G.add_edge(3, 5, weight=4)
G.add_edge(4, 5, weight=6)

# 全点対最短経路を求める
all_shortest_paths = dict(nx.shortest_path(G))

# 結果を表示する
for source in all_shortest_paths:
    for target in all_shortest_paths[source]:
        if source != target:
            print(f"{source} から {target} までの最短経路: {all_shortest_paths[source][target]}")

まず、グラフを定義します。

nx.Graph() によって空の無向グラフを定義し、add_nodes_from メソッドを使用して頂点を追加し、add_edge メソッドを使用して辺を追加しています。

また、各辺には weight 属性を設定して、重みつきグラフとして定義しています。

次に、shortest_path 関数を使用して、すべての頂点のペアの最短経路を求めます。

ただし、この方法は全点対最短経路を求めるために必要な計算量が大きくなってしまい、大きなグラフには適用しづらい場合があります。

[実行結果]
1 から 2 までの最短経路: [1, 2]
1 から 3 までの最短経路: [1, 3]
1 から 4 までの最短経路: [1, 4]
1 から 5 までの最短経路: [1, 3, 5]
2 から 1 までの最短経路: [2, 1]
2 から 3 までの最短経路: [2, 3]
2 から 4 までの最短経路: [2, 4]
2 から 5 までの最短経路: [2, 3, 5]
3 から 1 までの最短経路: [3, 1]
3 から 2 までの最短経路: [3, 2]
3 から 4 までの最短経路: [3, 4]
3 から 5 までの最短経路: [3, 5]
4 から 1 までの最短経路: [4, 1]
4 から 2 までの最短経路: [4, 2]
4 から 3 までの最短経路: [4, 3]
4 から 5 までの最短経路: [4, 5]
5 から 3 までの最短経路: [5, 3]
5 から 4 までの最短経路: [5, 4]
5 から 1 までの最短経路: [5, 3, 1]
5 から 2 までの最短経路: [5, 3, 2]

すべての頂点のペアの最短経路を求めることができました。