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$.
Shortest paths among two subsets of nodes
graphs;graph theory;shortest path
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$.