Python
networkx

全頂点間の最短経路と最短距離を手抜きで求める試行錯誤した結果

タイトルの通り,あるグラフ$G$が与えられたとき,全頂点ペアで最短経路と最短経路を求めたい.

学術的にちゃんと意味のある問題だと思うし,おそらく世の中にちゃんとした実装が落ちていると思うけど,なんとかNetworkxだけがインストールされた劣悪な環境で怠けてこれを計算できないかと考えた.

もし5秒ぐらいでインストールできるライブラリがあったら教えてください.


gist

https://gist.github.com/cocomoff/b8fa77e4dd24a1216ff37edb8aa03d50


欲しいもの


  • 頂点間距離

  • 頂点間の最短経路


組合せで頑張る

特に何も工夫せずに,普通に最短経路と距離を計算する方法も考えられる(明らかに辛い).

例えばnx.shortest_pathnx.shortest_path_lengthが使える.ある頂点$v$だけを固定した場合に結果としてdictが帰ってくる様子なので,効率化ができそう.実際は$u < v$だけを格納すればいいと思うけど,とりあえずわざわざ反転して保存しておく.

#手抜き1

def build_stpath_naive(G):
distG = {}
pathG = {}
for (v, u) in product(G.nodes(), G.nodes()):
if v > u:
continue
path = nx.shortest_path(G, v, u, weight='weight')
lpath = nx.shortest_path_length(G, v, u, weight='weight')
distG[(u, v)] = distG[(v, u)] = round(lpath, 4)
pathG[(u, v)] = path[::-1]
pathG[(v, u)] = path
return distG, pathG


既存実装で頑張る

困ったときは公式ドキュメントを確認する癖が大事.

networkxのドキュメントを見ていると,all_pairs_dijkstra_path_lengthall_pairs_bellman_ford_pathなどがイテレータを返す用途の実装に見えるので使えそう.とりあえず,generatorをdictに変換して,他の実装とアクセス方法を揃えておいた.

def build_stpath_functions(G):

pathG = dict(all_pairs_dijkstra_path(G))
distG = dict(all_pairs_dijkstra_path_length(G))
ddistG = {(u, v): round(distG[u][v], 4) for u in distG for v in distG[u]}
ppathG = {(u, v): pathG[u][v] for u in pathG for v in pathG[u]}
return ddistG, ppathG


計算結果を記録する

少しだけ考えると,ある最短経路$p$上のすべての部分経路は最短経路になっている.

そのためこれを記録して保存していき,まだ計算されていない頂点対$(u, v)$についてのみ保存しておくという手法が実装できる.

def build_stpath_memo(G):

distG = {(u, u): 0 for u in G.nodes()}
pathG = {(u, u): [] for u in G.nodes()}
constructed = set({})
for (v, u) in product(G.nodes(), G.nodes()):
if v > u or (v, u) in constructed or (u, v) in constructed:
continue
path = nx.shortest_path(G, v, u, weight='weight')
lpath = nx.shortest_path_length(G, v, u, weight='weight')
pathG[(u, v)] = path[::-1]
pathG[(v, u)] = path
distG[(u, v)] = distG[(v, u)] = round(lpath, 4)
constructed.add((v, u))
constructed.add((u, v))

lpath1 = lpath
for idx in range(1, len(path)):
pathI = path[idx:]
vi = path[idx]
lpath1 -= G[path[idx - 1]][path[idx]]['weight']
if (vi, u) not in constructed or (u, vi) not in constructed:
pathG[(vi, u)] = pathI
pathG[(u, vi)] = pathI[::-1]
distG[(vi, u)] = distG[(u, vi)] = round(lpath1, 4)
constructed.add((vi, u))
constructed.add((u, vi))

lpath2 = lpath
for idx in range(len(path) - 2, 1, -1):
ui = path[idx]
lpath2 -= G[path[idx]][path[idx + 1]]['weight']
if (v, ui) not in constructed or (ui, v) not in constructed:
pathI = path[:idx + 1]
pathG[(v, ui)] = pathI
pathG[(ui, v)] = pathI[::-1]
distG[(v, ui)] = distG[(ui, v)] = round(lpath2, 4)
constructed.add((v, ui))
constructed.add((ui, v))
return distG, pathG


比較

適当に歪めた格子グラフを作成して計算時間を比較した

環境はThinkpad T480s Core i7-8550U@1.80GHz, 16GB memory

格子グラフの1辺のサイズ
手法1(naive)
手法2(functions)
手法3(memo)

5
0.0048
0.0489
0.0154

7
0.0207
0.1708
0.0809

9
0.0746
0.6292
0.2705

11
0.1230
2.1338
0.7561

13
0.2656
5.8495
1.9621

15
0.4720
13.9250
4.3266

17
0.8449
31.3541
8.9448

19
1.1926
60.3808
16.8544

21
2.1525
115.8890
32.3284

23
2.8630
200.9873
50.1435

25
3.8957
349.2804
89.4872


結論

公式ドキュメント読め