You're given a directed weighted graph, which has m edges and n vertices. Every edge's weight is nonnegative. The vertices are either in set S1 or in set S2 (S1 and S2 are disjoint). You need to find the shortest path between any pairs (v1, v2) (v1 is in S1, and v2 in S2).

The running time of the solution should be O(mlogn).

'Nonnegtive' and 'mlogn' remind me of Dijkstra, but I have no idea how to use Dijkstra for constant times to solve it.

Thanks in advance.

CodePudding user response：

Dijkstra, but modified:

1. Initialize

   double min = infinite;     // shortest distance between n1 (of s1) and n2 (of s2)
   Node n1 = null, n2 = null; // members of s1 and s2 with shortest distance between them
   Set<Node> visited = new Set<>(); // initially-empty set of visited nodes of s1
   

2. Run Dijkstra from each node of s1 until

   a. you reach a node of s2 (add start node to visited; if distance < min, update min, n1 and n2)

   b. you reach a node of s1 that is already in visited (add the start node to visited)

   c. you run out of nodes to visit (possible only if graph is not connected; add the start node to visited)

3. Return result pair.

Running Dijkstra is O(m log n) worst-case, but you will not be running it fully |s1| times - instead, the end result of the above steps is equivalent or faster (in terms of edges visited) to running Dijkstra fully just once per connected component. Therefore, the whole algorithm is O(m log n)