Optimal set of shortest paths from one node to all others in a network graph

Question

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

Answer 1

Your problem can be solved in the same time needed to compute a shortest-path tree of your graph. See Theorem 3 in the paper "Balancing Minimum Spanning Trees and Shortest-Path Trees" by Khuller et al. which also deals with directed graphs.

Essentially you want to find a minimum-weight branching (directed spanning tree) of the subgraph $H$ containing all edges that belong to some shortest path from the source vertex.

Once the distances $d(v)$ from the source to every vertex $v$ are known, $H$ can be found in linear time (simply check, for each edge $(u,v)$, whether $d(u)+w(u,v)=d(v)$, where $w(u,v)$ is the weight of edge $(u,v)$). Then, the paper gives an easy linear-time algorithm to find a minimum-weight branching from $H$. If there are no edges of weight 0 in your original graph (and hence in $H$) the algorithm boils down to selecting, for each vertex $v$, the minimum-weight edge among those entering $v$ in $H$.

If there are edges of weight 0, you can first contract all those edges and then apply the above strategy. The selected edges plus the contracted edges form a graph of minimum weight containing at least one shortest path from the source towards every other vertex.