python - Saving shortest paths VS computing shortest paths

Question

I have a graph of n nodes and throughout my function, I use the shortest paths from one node to another and I may need to use the same path several times. Should I save shortest paths of all combinations of nodes in a dictionary like so:

shortest_paths = {}
cells = graph.keys() # graph is a dictionary which represents the graph
for cell_o in cells:
   print(cell_o,'/',len(graph))
   for cell_d in cells:
      shortest_paths[(cell_o, cell_d)] = compute_shortest_path(cell_o, cell_d, graph)

and access the dictionary anywhere in the function to find paths from cell1 to cell2 like so:

path = shortest_paths[(cell1, cell2)]

or should I compute the shortest paths each time I need it like so:

path = compute_shortest_path(cell1, cell2, graph)

In order to optimize for execution time, what choice should I make? Should this decision be based on the number of nodes (n), the number of connections of nodes (n), the number of times I need the shortest paths in a function, my computer specifications?

question from:https://stackoverflow.com/questions/65913641/saving-shortest-paths-vs-computing-shortest-paths

Answer 1

Waitting for answers