このコードの時間の複雑さを減らす方法は？

Question

グラフG=(V,E)を持っています。NODEのノードVサブセットのリスト。NODEの各ノードの隣接ノードのすべての隣接ノードを見つけて、それらの隣人が2を超える距離を持つ場合はエッジを追加したいと思います。

import networkx as nx
import random

G = nx.erdos_renyi_graph(30, 0.05)

node=[]
for j in range(5): 
        node.append(random.randint(1,30))

for i in node:
    lst=list(G.neighbors(i))
    if(len(lst)>1):
         for j in range(len(lst)):
             for k in range(j+1,len(lst)):
                 if(len(nx.shortest_path(G,lst[j],lst[k]))>2):
                     G.add_edge(lst[j],lst[k])

.

Answer 1

二次時間を取得するには、次の手順を実行します。

$ m= n（\ text {node}）$ $ g $

compute $ g '=（g - \ text {node}）^ 3 $ 、 2nd $ G $ 。

次のことを実行します。 $ u $ 、 $ m $ 、 $ uv \ notin e（g '）$ の場合、 $ uv $ $ g $ 。

このようにあなたはもうshortest_pathを計算する必要はありません。