TL;DR How to convert a geodataframe of LineStrings to a Complete Graph with NetworkX?

I have a geodataframe of a collection of linestrings that geographically represent a road network (purple). I have 2 points (red and blue) representing A and B. I’d like to find the shortest route between A and B travelling along the road network.

I have converted the geodataframe to a network using momepy library:

road = gpd.read_file(input_road.shp)

#need to explode roads, as is multiline
exploded = road.explode(index_parts=True)

G = momepy.gdf_to_nx(exploded, approach="primal",length='mm_len',multigraph=True)

This successfully converts my road network to a networkx multigraph, whilst preserving distance (mm_len) between points.

Then I add points A and B to the network by getting the closest nodes on the road network to these points:

my_points = gpd.read_file(my_points)

#Firstly, need to convert the coordinates to a tuple of x,y coordinates
for my_point in my_points .geometry.values:
    coords_values = re.findall('[0-9.]+ [0-9.]+', str(my_point ))
    
    #convert list of strings separated by spaces, to a list of coords as list. 
    coords = [sub.split(' ') for sub in coords_values ][0]
    coords_tuple= tuple(map(float, coords ))
    coords_list.append(coords_tuple)

#add this coord tuple as a column in the dataframe
my_points["coords_syntax"] = coords_list

#this dictionary will be used to select the network nodes. The key is the coordinate tuple, and the attribute will be the 'Name' of the point
dict_df_mypoints = home.set_index('coords_syntax')['Name'].to_dict()   

#select the nearest node points on the road network to these coordinate tuples
A = list(G.nodes())

#iterate through dict of coords: my_points
for point in dict_df_mypoints :
    
    
    #get closest node (using KDTree) between point and the array of cords A generated above
    closest_node = A[scipy.spatial.KDTree(A).query(point)[1]]
    
    #make these above closest nodes have attribute my_point, with other attributes (dict_df[point])
    G.nodes[closest_node]['my_point'] = dict_df[point]

So now within all the nodes of my road network, I have 2 representing points A and B respectively. Their node key is the coordinate pair.

However, when I run the shortest_path algorithm between A and B I get this error:

nx.shortest_path(G,source = (455529.02164326626, 206374.9504608615),target = (454340.3426543578, 207204.53480888018))


>>NetworkXNoPath: No path between (455529.02164326626, 206374.9504608615) and (454340.3426543578, 207204.53480888018)

And when I check the edges of these nodes, they are only connected to their 2 neighbours, and no other node:

nx.single_source_shortest_path_length(G,source = (455529.02164326626, 206374.9504608615))

 >>{(455529.02164326626, 206374.9504608615): 0,
 >>(455582.6204962559, 206424.4603359318): 1,
 >>(455596.5948359391, 206455.62556823122): 2}

So these nodes need to all be connected to one another with edges, otherwise the shortest_path won’t work. I need to make my network a Complete Graph. However, I have no idea how to do that- it can’t be done with Momepy. However I am unsure how to create a NetworkX Graph from scratch whilst preserving the geographical distances between the nodes of the roadnetwork – this is what drew me to using Momepy in the first place. Advice would be appreciated, thanks 🙂