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$.
$\begingroup$
$\endgroup$
3
-
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. ♦Commented Jun 4, 2017 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$– hengxinCommented Jun 4, 2017 at 2:41
-
$\begingroup$ @D.W. Now I think the method of "adding extra nodes" works. Thanks. $\endgroup$– hengxinCommented Jun 4, 2017 at 2:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.