¿Cómo reducir la complejidad temporal de este código?

Question

tengo un grafico G=(V,E).Una lista de nodos NODE subconjunto de V.Quiero conocer todos los nodos vecinos de cada nodo en NODE y agregue borde si esos vecinos tienen una distancia mayor que 2.¿Alguien aquí puede ayudarme a reducir la complejidad temporal de este código a tiempo cuadrático o menos?

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

Para obtener el tiempo cuadrático, haga lo siguiente:

Dejar $M = N( ext{NODO})$ ser los vecinos de NODE en $g$.

Calcular $G' = (G - ext{NODO})^3$, el 2do gráfico de potencia de $g$ sin los vértices de NODE.

Luego haces lo siguiente:Por cada dos vértices $u$ y $v$ en $M$, si $uv otin E(G')$, agregar $uv$ a $g$.

De esta manera no tienes que calcular shortest_path ya no.