3
$\begingroup$

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes $\mathrm{dist}(S, P_i) + \mathrm{dist}(D, P_i)$? In addition, the overall path from $S$ to $D$ should contain only one node from the set $A$. What is an efficient algorithm for this? I don't want to go with brute-force approach.

$\endgroup$
  • $\begingroup$ Is this not the same as finding the shortest path from S to D? $\endgroup$ – sjmc Apr 8 '14 at 19:56
  • 1
    $\begingroup$ @sjmc it isn't because the shortest path between $S$ and $D$ may shunt the set $A$ $\endgroup$ – collapsar Apr 8 '14 at 20:15
  • $\begingroup$ @sjmc I disagree. Shortest path takes all the intermediate nodes into consideration where OP is only interested in a subset of those. Projecting the graph on (S, D} union A, and then doing shortest path is also wrong because distance(S, Pi) can go through nodes not in A. $\endgroup$ – Tushar Apr 8 '14 at 20:15
  • $\begingroup$ Ah I misunderstood what was meant by "intermediate nodes". You're both right, it's of course not the same. $\endgroup$ – sjmc Apr 8 '14 at 20:22
4
$\begingroup$

The following answers the variant which requires passing through the set exactly once.

Make two copies of the graph. Remove all edges incident to two vertices of $A$. Orient all edges incident to $A$ in the first copy toward $A$, and all edges incident to $A$ in the second copy from $A$; other edges are bidirectional. Connect both copies of each vertex in $A$ with a zero-weight edge going from the first copy to the second copy. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

Using Dijkstra's algorithm, the complexity of this approach is $O(E+V\log V)$. In comparison, the trivial algorithm that tests all vertices in $|A|$ one at a time needs to run Dijkstra's algorithm $|A|$ times, unless the graph is unweighted, in which case one can use BFS instead in time $O(E|A|)$.


Here is an alternative solution, using only undirected graphs. Start by deleting all edges inside $A$. Add $M$ to the weight of all other edges incident to $A$, where $M$ is larger than the sum of all weights in the graph. Run Dijkstra's algorithm twice to find the shortest path between $S$ and any vertex in $A$, and between $T$ and any vertex in $A$; in both cases, the shortest path passes through no other vertex in $A$, due to our adjustment of the weights. Now go over all vertices $A$ and find the shortest path from $S$ to $T$ via a vertex in $A$.

This algorithm also runs in time $O(E+V\log V)$.


The following answers the variant which requires passing through the set at least once.

Make two copies of the graph. Connect both copies of each vertex in $A$ with an edge of zero weight. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

The complexity is $O(E+V\log V)$, or $O(E+V)$ if the original graph is unweighted (in this case, we modify the construction so that the parallel $A$-edges have unit weight; this is harmless in terms of computing the shortest path).

$\endgroup$
  • $\begingroup$ @YuvalFilmus , minimum number of computation is desired. But your solution [ I suppose it may work ] makes even the computation worse. $\endgroup$ – K.Nath Apr 9 '14 at 14:54
  • $\begingroup$ @K.Nath According to Wikipedia, Dijkstra's algorithm can be implemented in time $O(E+V\log V)$, which is better than the trivial $O(E|A|)$ solution unless the graph is very sparse and $|A|$ is very small. $\endgroup$ – Yuval Filmus Apr 9 '14 at 15:01
  • $\begingroup$ How does your algorithm(s) guarantee that the output trail is actually is a path? $\endgroup$ – Untitled Apr 13 '15 at 7:06
1
$\begingroup$

One way of doing this would be reducing it to |A| shortest path problems. Every shortest path would be on the subgraph G - A + {Pi} for a Pi. This will give minimum [ distance(S, Pi) + distance(D, Pi) ] for that Pi. Choose the Pi for which the shortest path is minimum.

EDIT: As @collapsar pointed out, this will only work if distance(S, Pi) does not include nodes in A-{Pi}. Not the answer you were looking for but it might give some ideas.

$\endgroup$
  • $\begingroup$ I think your algorithm is not correct: The shortest path from $S$ to $D$ through $P_i$ may pass through some $P_j, j\not=i$. You won't capture it by computing in $(G \setminus A) \cup {P_i}$. As a border case, consider the shortest path from $S$ to $D$ in $G$ passing through every $P_i$. $\endgroup$ – collapsar Apr 8 '14 at 20:46
  • $\begingroup$ If it passes through Pj, then the shortest distance through Pj would be less than equal to Pi. Hence, Pi won't be chosen. My understanding of the question was that distance(S, Pi) could involve any node. $\endgroup$ – Tushar Apr 8 '14 at 20:50
  • 2
    $\begingroup$ Consider the complete graph. Assume in path $S, P_1, \dots, P_n, D$ all edge weights are 1. Also assume that all other edge weights are 'sufficiently large' (eg $> |V(G)|^2$). your algorithm would not find the shortest path between $S$ and $D$ passing through $A$ because it had to consider all of $A$ which it doesn't. $\endgroup$ – collapsar Apr 8 '14 at 21:04
  • $\begingroup$ Oh I see. You are correct. My answer would only get correct answer if distance(S, Pi) should not involve any nodes in A - {Pi}. $\endgroup$ – Tushar Apr 8 '14 at 21:09
  • $\begingroup$ @Tushar , you are quite right. I need such a shortest path from S to D that includes only one node from set A, i.e; I need an algorithm that can choose only one Pi from set A for which dist(S, Pi) + dist(D, Pi) is minimum. Can you give me any reference or implementation idea for this algorithm? Is it |A| shortest path algorithm ? $\endgroup$ – K.Nath Apr 9 '14 at 8:37

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.