how to reduce the time complexity of this code?
To get quadratic time, do the following:

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.