Let's say I have a country with a set of cities, which I represent on the network graph below as a set of nodes. Furthermore, the weighed edge between pairs of nodes, represent the distance by road between them. I'll define the capital city as node A. There is no direct route between A and C so there is no edge between them.
I want to keep all the roads in my country that represent the shortest path from the capital A to all other cities. I then want to remove all other roads. However, I want to find the solution which allows me to remove the largest distance of road possible.
If we look at my network below, the solution in this case is to remove the edge between C and D. By doing so, I can still visit B, C, or D from A at the shortest possible distance and I have removed road of length 3. If I instead removed the road between B and C, I would have only removed road of length 2, so this is not the solution I am looking for.
How might I go about solving this problem? I'm using networkx and Python and I can use the the function nx.all_shortest_paths() to return the shortest paths between two cities. However I can't figure out which path to choose when I have several options like this. Obviously there can be much more complex examples than that provided here. So to clarify, I want to remove the largest sum of road not needed. That is, the sum of the edge weights removed should be a maximum.
I've also post my question on stack overflow: https://stackoverflow.com/questions/69306867/optimal-set-of-shortest-paths-from-one-node-to-all-others-in-a-network-graph