Come ridurre la complessità del tempo di questo codice?

Question

Ho un grafico G=(V,E).Un elenco di nodi NODE sottoinsieme di V.Voglio scoprire tutti i nodi vicini di ciascun nodo in NODE e aggiungere il bordo se quei vicini hanno una distanza maggiore di 2. Qualcuno può aiutarmi a ridurre la complessità del tempo di questo codice a tempo quadratico o meno.

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

Per ottenere il tempo quadratico, effettuare le seguenti operazioni:

Let $ M= n (\ testo {nodo}) $ Sii i vicini del nodo in $ G $ .

Compute $ g '= (g - \ text {node}) ^ 3 $ , 2nd Grafico di alimentazione di $ G $ senza i vertici dal nodo.

Quindi fai quanto segue: per ogni due vertici $ U $ e $ v $ in $ m $ , se $ UV \ NOTIN E (G ') $ , aggiungi $ UV $ a $ G $ .

In questo modo non è necessario calcolare più shortest_path.