Optimizing python script to produce output faster (Variable Assignment)

I am using python for optimization purposes. I made a graph using Networkx library with 1100 nodes. The python script includes the following lines.

# Compute key parameters of MIP model formulation
from itertools import product
num_facilities = len(facilities)
print("The num_facility = ", num_facilities)
num_customers = len(customers)
print("The num_customers = ", num_customers)
cartesian_prod = list(product(range(num_customers), range(num_facilities))) 

#Output
The num_facility =  1100
The num_customers =  1100

In the next step, some random numbers are generated as follows:

import random
random.seed(7) 
number_of_vpns = random.sample(range(0, 1200), num_facilities)

I compute the distance between nodes in the graph using the following function.

def compute_distance(source_number,dest_number):
    path = (nx.shortest_path(g,source=source_number,target= dest_number, weight='weight'))
    path_length = path_weight(g, path, weight="weight")
    return path_length

Finally, I defined the variable “shipping_cost” as:

%%time
shipping_cost = {(c,f): number_of_vpns[c]*compute_distance(c,f) for c, f in cartesian_prod}

Every line of the above code is executed in short manner (milliseconds). But, the assignment the value to the variable “shipping_cost” is not completed even after 7 hours. The variable logically contains 1210000 values.

1. Does it seem normal in terms of running time?
2. Is there any way to decrease the execution time of shipping_cost assignment?

Answer

Based on the comments by @Ram:

The cartesian_prod contains 1210000 values. The code is calling compute_distance() which in turn calls shortest_path() and path_length()for all the 1210000 values from networkx library. That’s the reason calculating shipping_cost takes lot of time to compute.

I changed the code as follows (path_lengths is added instead of compute_distance and shipping_cost is modified):

import networkx as nx
path_lengths = dict(nx.all_pairs_dijkstra_path_length(g, weight='weight'))

shipping_cost = {(c,f): number_of_vpns[c]*path_lengths[c][f] for c, f in cartesian_prod}

By doing so, the path_lengths is calculated once for all nodes, and the time complexity is focused on accessing the elements of path_lengths.