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

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

gist

欲しいもの

• 頂点間距離
• 頂点間の最短経路

組合せで頑張る

特に何も工夫せずに，普通に最短経路と距離を計算する方法も考えられる（明らかに辛い）．
例えばnx.shortest_pathやnx.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_lengthやall_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

結論

公式ドキュメント読め