1
$\begingroup$

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

enter image description here

$\endgroup$
3
  • $\begingroup$ Another related question. $\endgroup$ Sep 24 at 8:00
  • $\begingroup$ @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. $\endgroup$
    – Baz
    Sep 24 at 8:05
  • $\begingroup$ @Inuyasha Yagami The largest sum of roads not need. I will update my question to make this clearer. $\endgroup$
    – Baz
    Sep 24 at 8:23
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.