如何降低这段代码的时间复杂度？

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( ext{节点})$ 是 NODE 的邻居 $G$.

计算 $G' = (G - ext{NODE})^3$, ， 这 第二名 功率图 的 $G$ 没有来自 NODE 的顶点。

然后您执行以下操作：对于每两个顶点 $u$ 和 $v$ 在 $M$, ， 如果 $uv otin E(G')$, ， 添加 $紫外线$ 到 $G$.

这样你就不必计算 shortest_path 不再了。