最短経路問題 NetworkX

最短経路問題

地図上の最短経路を見つける最短経路問題（Shortest Path Problem）を考えます。

以下のコードは、2つの地点間の最短経路を見つけ、結果を分かりやすくグラフ化します。

これにはNetworkXとMatplotlibを使用します。

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
27
28
29
30
31
32
33
34
35
36
37
38
import networkx as nx
import matplotlib.pyplot as plt

# グラフを作成
G = nx.Graph()

# 都市とその座標を追加
G.add_node("A", pos=(0, 0))
G.add_node("B", pos=(2, 4))
G.add_node("C", pos=(4, 0))
G.add_node("D", pos=(6, 4))

# 都市間の距離を追加
G.add_edge("A", "B", weight=4)
G.add_edge("A", "C", weight=4)
G.add_edge("B", "C", weight=3)
G.add_edge("B", "D", weight=2)
G.add_edge("C", "D", weight=5)

# 最短経路を計算
shortest_path = nx.shortest_path(G, source="A", target="D", weight="weight")

# グラフを描画
pos = nx.get_node_attributes(G, "pos")
labels = {node: f"{node}" for node in G.nodes()}

plt.figure(figsize=(8, 6))
nx.draw(G, pos, with_labels=True, labels=labels, node_size=3000, node_color="skyblue", font_size=12)
edge_labels = nx.get_edge_attributes(G, "weight")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=12)
nx.draw_networkx_edges(G, pos, edgelist=[(shortest_path[i], shortest_path[i+1]) for i in range(len(shortest_path)-1)], edge_color="red", width=2)
plt.title("Shortest Path", fontsize=16)
plt.axis("off")
plt.show()

# 最短経路とその距離を表示
print("Shortest Path:", shortest_path)
print("Shortest Distance:", nx.shortest_path_length(G, source="A", target="D", weight="weight"))

このコードは、地図上の複数の都市（A、B、C、D）とそれらの座標を表すノードを持つグラフを作成し、各都市間の距離を追加します。

そして、最短経路を見つけ、グラフで視覚化し、最短経路とその距離を表示します。

ソースコード解説

以下はコードの詳細な説明です。

1. ライブラリのインポート:

  • networkx（ネットワーク分析のためのライブラリ）とmatplotlib.pyplot（グラフ描画のためのライブラリ）をインポートします。

2. グラフの作成:

  • G = nx.Graph() で、新しいグラフオブジェクト G を作成します。
    このグラフは、都市と都市間の関係を表現します。

3. 都市と座標の追加:

  • G.add_node() を使用して、都市名とそれに対応する座標を追加します。
    例えば、都市 “A” の座標は (0, 0) です。
    これらのノードはグラフ上で都市を表します。

4. 都市間の距離の追加:

  • G.add_edge() を使用して、都市間の距離を追加します。
    weight パラメータはエッジの重み（距離）を指定します。
    例えば、都市 “A” から “B” までの距離は 4 です。

5. 最短経路の計算:

  • nx.shortest_path() 関数を使用して、指定した2つの都市間の最短経路を計算します。
    ここでは、都市 “A” から “D” までの最短経路を計算しています。

6. グラフの描画:

  • グラフの描画には nx.draw() メソッドを使用します。
    pos パラメータにはノードの座標情報が含まれ、with_labels パラメータを True に設定すると、ノードにラベルが表示されます。
  • エッジの重み（距離）は nx.draw_networkx_edge_labels() を使用してエッジ上に表示され、最短経路は赤い線で強調表示されます。

7. グラフのタイトルと軸ラベル:

  • グラフのタイトルは plt.title() を使用して設定され、”Shortest Path” と表示されます。
  • plt.axis("off") は軸を非表示にし、より視覚的にきれいな描画を提供します。

8. 最短経路と距離の表示:

  • 最短経路とその距離は print() ステートメントを使用してコンソールに表示されます。
    最短経路は “Shortest Path” として表示され、距離は “Shortest Distance” として表示されます。

このコードは、都市間の最短経路を計算し、視覚的に表現するためのもので、最適な経路を見つける手法を示しています。

グラフ解説

上記のコードによって生成されるグラフは、地図上のいくつかの都市と都市間の最短経路を視覚的に表現します。

以下にその詳細を説明します。

1. グラフの構築:

  • このグラフは、NetworkXを使用して構築されます。
    各都市はグラフのノードとして表され、都市間の距離はエッジ（辺）として表現されます。
  • “A”、”B”、”C”、”D” という4つの都市があり、それぞれの座標が指定されています。

2. エッジの追加:

  • 各都市間の距離は G.add_edge() メソッドを使用して追加されます。
    例えば、都市 “A” から都市 “B” への距離は4、都市 “B” から都市 “C” への距離は3となっています。

3. 最短経路の計算:

  • nx.shortest_path() 関数は、指定した2つの都市（ここでは “A” から “D”）間の最短経路を計算します。
    この経路は shortest_path 変数に格納されます。

4. グラフの描画:

  • nx.draw() メソッドを使用して、グラフを描画します。
    各都市はノードとして表示され、都市間の距離がエッジに表示されます。
  • 最短経路は赤い線で示され、最短経路のエッジには距離がラベルとして表示されます。

5. グラフの表示:

  • plt.show() を使用して、グラフが表示されます。このグラフは Matplotlib を使用して描画され、都市とエッジは視覚的に分かりやすく表現されます。

6. 最短経路と距離の表示:

  • 最短経路とその距離は、グラフの描画の下に表示されます。
    例えば、”A” から “D” までの最短経路は “A” -> “B” -> “D” で、その距離は 6 です。

このグラフは、地図上の都市間の最短経路を可視化し、最適な経路を見つけるために使用できる手法の一例です。