# how to reduce the time complexity of this code?

I have a graph G=(V,E). A list of nodes NODE subset of V. I want to find out all the neighbor nodes of each node in NODE and add edge if those neighbors have distance greater than 2. Can anyone here please help me to reduce the time complexity of this code to quadratic time or less.

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):

• As presented, this looks a programming problem. Check out stackoverflow and CodeReview@SE. Commented Jun 4, 2020 at 7:19
• @greybeard I don't agree. This is an algorithmic question. What is the best algorithm to find pair of vertices whose distance exceed 2. Commented Jun 4, 2020 at 7:20
• @PålGD Please see the caption of tag python. I think the very same question would be on topic if presented differently. Commented Jun 4, 2020 at 7:23
• I see the tag, but when you put it like that, it seems like the python tag is a catfishing mechanism. Commented Jun 4, 2020 at 7:25
• – D.W.
Commented Jun 4, 2020 at 18:22

Let $$M = N(\text{NODE})$$ be the neighbours of NODE in $$G$$.
Compute $$G' = (G - \text{NODE})^3$$, the 2nd power graph of $$G$$ without the vertices from NODE.
Then you do the following: For every two vertices $$u$$ and $$v$$ in $$M$$, if $$uv \notin E(G')$$, add $$uv$$ to $$G$$.
This way you don't have to compute shortest_path anymore.