最短経路¶
NetworkX のドキュメントから shortest path を検索すると、かなりの個数の最短経路計算関数がリストされる。求めたい最短経路の種類に応じて適切なアルゴリズムを実装している関数を採用する能力が必要だ。候補となるアルゴリズムは、特定の二ノード間の経路だけ求めたいのか、あるいはある固定されたノードと他の到達可能なノードすべてとの経路を求めたいのか、経路というのはエッジ列だけで十分なのか、あるいは重みのトータルが必要なのか、はたまたグラフエッジの重みが重要なのか否か、重みの非負性は必要なのか、等の与えられた問題の制約で決まる。
といっても、実際に使う関数は毎回顔ぶれが決まっていることが多い。本稿では、そのような利用頻度の高いものについて記す。
共通ルール¶
最短経路計算関数すべての共通ルールについて記す。
エッジの重みは、定義するのであれば、数値とする。
Dijkstra 系の関数に与えるグラフのエッジの重みは非負性が必要と思え。
キーワード引数
weightを明示的に指定する場合、エッジの属性の名前を文字列で指定する。キーワード引数
weightはデフォルト値Noneまたは指定された属性を持たぬエッジがある場合、関数はそのようなエッジに対しては、重みが 1 であるかのように取り扱って経路を計算する。キーワード引数
cutoffは探索の深さまたは経路長の上限を指定することができる。その関数が引数
weightを提供しない場合、単に探索の深さを指定する。つまり、戻り値の（個々の）経路のエッジ本数がcutoffを超えない。その関数が引数
weightを提供する場合、経路長の上限を指定することになる。つまり、戻り値の（個々の）経路のエッジの重み総和がcutoffを超えない。
関数
all_pairs_xxxxはsingle_source_xxxxの簡単な反復呼び出しで実装されている。
Dijkstra 法による最短経路探索関数¶
エッジの重みがノード間の道のりだとか、交通料金だとか、移動時間だとかを表現するようなグラフでは、最短経路を求めるためのアルゴリズムとして Dijkstra 法を採用しておけば無難だ。
以前行った、別のグラフライブラリーの試験に用いた問題設定を再利用する。問題は 最短経路計算対象グラフ に示すグラフのエッジの重みがノード間の道のりを示すと仮定した上で、 「すべてのノードペアに対して、その最短経路の長さを得る」とする。
ここでは当然関数 all_pairs_dijkstra_path_length を利用する。グラフの定義から最短経路の長さを計算するまでの処理を行うコードは次のようなものになる。
#!/usr/bin/env python
"""dijkstra.py: all_pairs_dijkstra_path demonstration
"""
import networkx as nx
from networkx.algorithms.shortest_paths.weighted import all_pairs_dijkstra_path_length
# Make a graph.
G = nx.DiGraph()
# Define edges with weights.
G.add_weighted_edges_from(
((0, 1, 10.0),
(0, 2, 14.0),
(0, 3, 12.0),
(1, 2, 8.0),
(1, 4, 19.0),
(2, 3, 7.0),
(2, 5, 22.0),
(3, 5, 21.0),
(4, 5, 11.0),))
# Compute the shortest path lengths between all nodes in graph G.
all_pairs = all_pairs_dijkstra_path_length(G)
for source, mapping in all_pairs:
for target in mapping.keys():
if source != target:
dist = mapping[target]
print(f"({source}, {target}): {dist:4.1f}")
実行結果は次のようなものになる。出力の見やすさにこだわりがなければ、単に
print(all_edges) でも各経路の最短距離を目視できる。インポートの手間に見合う結果が得られたのではないかな。
(0, 1): 10.0
(0, 3): 12.0
(0, 2): 14.0
(0, 4): 29.0
(0, 5): 33.0
(1, 2): 8.0
(1, 3): 15.0
(1, 4): 19.0
(1, 5): 30.0
(2, 3): 7.0
(2, 5): 22.0
(3, 5): 21.0
(4, 5): 11.0
負のエッジの重みを許す最短経路探索関数¶
Todo
気の利いた例を提示する。
A* アルゴリズムによる最短経路探索関数¶
Todo
気の利いた例を提示する。特に Dijkstra v.s. A* などをやりたい。
