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

タイトルの通り，あるグラフ$G$が与えられたとき，全頂点ペアで最短経路と最短経路を求めたい．
学術的にちゃんと意味のある問題だと思うし，おそらく世の中にちゃんとした実装が落ちていると思うけど，なんとかNetworkxだけがインストールされた劣悪な環境で怠けてこれを計算できないかと考えた．
もし5秒ぐらいでインストールできるライブラリがあったら教えてください．

# gist

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

### 欲しいもの
- 頂点間距離
- 頂点間の最短経路


# 組合せで頑張る

特に何も工夫せずに，普通に最短経路と距離を計算する方法も考えられる（明らかに辛い）．
例えば**nx.shortest_path**や**nx.shortest_path_length**が使える．ある頂点$v$だけを固定した場合に結果としてdictが帰ってくる様子なので，効率化ができそう．実際は$u < v$だけを格納すればいいと思うけど，とりあえずわざわざ反転して保存しておく．

```python
#手抜き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_length**や**all_pairs_bellman_ford_path**などがイテレータを返す用途の実装に見えるので使えそう．とりあえず，generatorをdictに変換して，他の実装とアクセス方法を揃えておいた．

```python
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)$についてのみ保存しておくという手法が実装できる．

```python
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 |

# 結論

公式ドキュメント読め