Edited at

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

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

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

# gist

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

• 頂点間距離

• 頂点間の最短経路

# 組合せで頑張る

```#手抜き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
```

# 計算結果を記録する

そのためこれを記録して保存していき，まだ計算されていない頂点対\$(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)

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)

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)
return distG, pathG
```

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