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

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

• Another related question. Commented Sep 24, 2021 at 8:00
• @Inuyasha Yagami My question relates to shortest-path tree from the perspective of a specific node. In my example above, I call that node the capital city A.
– Baz
Commented Sep 24, 2021 at 8:05
• @Inuyasha Yagami The largest sum of roads not need. I will update my question to make this clearer.
– Baz
Commented Sep 24, 2021 at 8:23

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$$.