как уменьшить временную сложность этого кода?

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$, 2-й график мощности из $G$ без вершин из NODE.

Затем вы делаете следующее:Для каждых двух вершин $у$ и $в$ в $М$, если $uv otin E(G')$, добавлять $уф$ к $G$.

Таким образом, вам не придется вычислять shortest_path больше.