comment réduire le temps de la complexité de ce code?

Question

J'ai un graphique G=(V,E).Une liste de nœuds NODE sous-ensemble de V.Je veux trouver tous les nœuds voisins de chaque nœud NODE et d'ajouter bord si ces voisins ont la distance de plus de 2.Quelqu'un peut ici s'il vous plaît m'aider à réduire la complexité du temps de ce code pour quadratique du temps ou moins.

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

Pour obtenir quadratique du temps, procédez de la manière suivante:

Laissez $M = N( ext{NOEUD})$ être les voisins du NŒUD $G$.

Calculer $G' = (G - ext{NOEUD})^3$, le 2ème graphe de la puissance de $G$ sans les sommets de NŒUD.

Ensuite, vous procédez de la manière suivante:Pour tous les deux sommets $u$ et $v$ dans $M$, si $uv otin E(G')$, ajouter $uv$ pour $G$.

De cette façon, vous n'avez pas à calculer shortest_path plus.