Given a directed graph $G = (V, E)$ with all edge weights being non-negative and two disjoint subsets of nodes $S, T \subseteq V$, design an algorithm to find the shortest paths among $S$ and $T$, (formally, $\min\{d(s,t): s \in S, t \in T\}$) in $O(m \log n)$ time, where $|V| = n$ and $|E| = m$.

  • 2
    $\begingroup$ Can you clarify the problem statement? Do you want $d(x,y)$ for each $x \in S, y \in T$? Or $\min \{d(x,y) : x \in S, y \in T\}$? Or something else? The former can't be done in $O(m \log n)$ time; just consider $S=V,T=V$, and you'll see that it would imply an all-pairs shortest-paths algorithm faster than any currently known. $\endgroup$ – D.W. Jun 4 '17 at 2:32
  • $\begingroup$ I see. This is translated from Chinese. My understanding is $d(x,y), \forall x \in S, y \in T$. This is probably wrong according to your argument. Therefore, I think it should be $\min \{d(x,y): x \in S, y \in T\}$. I will edit the problem. Thanks. $\endgroup$ – hengxin Jun 4 '17 at 2:41
  • $\begingroup$ @D.W. Now I think the method of "adding extra nodes" works. Thanks. $\endgroup$ – hengxin Jun 4 '17 at 2:49

Note: The first version of my problem is to find all $d(s,t)$ for each $s \in S$ and $t \in T$. As @D.W. argues, it is not likely to do this in $O(m \log n)$ time because taking $S, T = V$ requires all pairs shortest paths. For $\min\{d(s,t): s \in S, t \in T\}$, however, the following method of "adding extra nodes" works:

  • Add an extra node $s_0$ and add edges of weights 0 from $s_0$ to each node in $S$
  • Add an extra node $t_0$ and add edges of weights 0 from each node in $T$ to $t_0$
  • Find the shortest path from $s_0$ to $t_0$.
| cite | improve this answer | |

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.