2

I have a graph data structure that has some source points (the red ones) and some destination points (the blue ones). I want to find the shortest path from every source point to its nearest destination point, or to its nearest source point that is already connected to a destination point by a shortest path.

Please see the image belowenter image description here

I can find the shortest path from multiple sources to multiple destinations, but the problem is in the bold part above.

The output of the algorithm should be a list of shortest paths that satisfy the above criteria, plus that the sum of all paths length is minimum.

The sequence of the algorithm should be something like this:

  1. Start by a source point, and find the shortest path to its nearest destination point.
  2. Take another source point, and find the shortest path to either the nearest destination point or to the source point that has been connected in step 1.
  3. Repeat step 2 until all source points are connected.

How can I do that? What is the name of this type of algorithm that can solve this problem?

D.W.
  • 159,275
  • 20
  • 227
  • 470
devfaz
  • 71
  • 4
  • Is every point/vertex in the graph either a red point (source) or blue point (destination)? Or could there be other vertices/points that are neither a source nor a destination (neither red nor blue)? – D.W. Oct 31 '22 at 21:27

2 Answers2

2

You can solve this in three stages, using a shortest-path algorithm followed by a minimum spanning arborescence algorithm.

Notation: Let $G$ be the original graph, with one vertex per point and the weight of each edge is the length of the path between those edges. Let $d(u,v)$ denote the length of the shortest path from $u$ to $v$ in $G$. The algorithm is as follows:

  • Stage 1: form a new directed graph $G'$, with one vertex per source vertex from $G$, plus one more vertex $r$. For each pair of sources $s_1,s_2$ from $G$, add to $G'$ an edge $s_2 \to s_1$ with weight $d(s_1,s_2)$. Also, for each source $s$, add an edge $r \to s$ with weight $\min_v d(s,v)$ where $v$ ranges over all destinations. Note that all of these distances can be computed using an appropriate shortest-path algorithm: e.g., by running Dijkstra's algorithm once per source.

  • Stage 2: find a minimum spanning arborescence for $G'$, with $r$ as the root. This can be done using Edmonds' algorithm, or more modern optimized versions of it.

  • Stage 3: do a pre-order traversal of the arborescence. Convert each edge $u \to v$ in the arborescence into the corresponding shortest path $v \leadsto u$ in $G$. Output these paths in the order given by the pre-order traversal.

The result of these three stages gives an optimal solution to your problem. The total running time is $O(|V| |E| + |V|^2 \log |V|)$, if you use Dijkstra's algorithm and Edmonds' algorithm in stages 1 and 2 respectively.

D.W.
  • 159,275
  • 20
  • 227
  • 470
0

This problem can be solved by minimum spanning tree (in time $O(n\log n + m)$).

Let $S$ be the set of sources and $T$ the set of destinations. Start by adding a vertex $u$ and make it adjacent to all destination vertices (with zero weight). Compute a minimum spanning tree of the resulting graph. You can choose the tree such that all edges between $u$ and $T$ are chosen (assuming no negative weights). We claim that by removing the edges between $u$ and $T$ we get an optimal solution of your problem.

Clearly in an optimal MST, each source vertex will have a path to $u$ that goes through some vertex of $T$. Hence, is a valid solution for your problem. On the other hand, given an optimal solution to your problem, clearly, no two paths overlap, since we can cut the overlapping part of some path and connect a source of one path to an endpoint of the other path. We also assume that no two destinations are connected in this solution, since we can remove an edge of the maximum height in the corresponding connected component getting a better solution. So by adding the vertex $u$ and packing all edges incident to it, we get a minimum spanning tree of the resulting graphs.

Narek Bojikian
  • 4,466
  • 1
  • 12
  • 35
  • That was a typo, corrected. Thanks! – Narek Bojikian Oct 31 '22 at 09:56
  • Can you help me understand what is meant by "cut the overlapping part of some path and connect a source of one path to an endpoint of the other path"? Could we have an optimal solution with one path of the form $s_1 \leadsto a \leadsto b \leadsto t_1$ and another path of the form $s_2 \leadsto a \leadsto b \leadsto t_2$? How would you transform that to obtain a solution without any overlap in the path? – D.W. Oct 31 '22 at 21:04
  • I am doubting your claim that no two paths overlap in an optimal solution. Suppose we have a graph with edges $(s_1,v)$ (weight 10), $(s_2, v)$ (weight 10), $(v, t)$ (weight 1), no other edges, and sources $S={s_1,s_2}$, destination $T={t}$. Then I think the optimal solution has two paths that overlap in the edge $v \to t$. What am I missing? – D.W. Oct 31 '22 at 21:08
  • Something seems wrong with the algorithm. Consider the graph with edges $(s,t)$, $(s,v)$, both of weight 1, $S={s}$, $T={t}$. Then your algorithm outputs a minimum spanning tree that contains both edges. But the optimal solution to the original problem contains only the edge $(s,t)$. I suspect perhaps you want the minimum-cost tree that spans all of $S \cup T \cup {u}$ and includes all of the edges $(t,u)$ where $t \in T$ (but it doesn't need to span all vertices of the graph). Is there an algorithm to find such a spanning tree? Can standard MST algorithms be adapted for that goal? – D.W. Oct 31 '22 at 21:15
  • oh I assumed $S\dot\cup T$ is a partition of the vertices of the graph. If not my solution will not work. – Narek Bojikian Oct 31 '22 at 21:25