Multi-start and Multi-end shortest path set

Question

I am having problem with shortest path in directed weighted graph. I know Dijkstra, BFS, DFS. However, I have a set of vertices S for starting points and a set of vertices E to end. S and E doesn't overlap. So how can I find the set of edges with minimal sum of edge weight? The edge set doesn't have to include all vertices in S, but have to reach all vertices in E. Should I start with Dijkstra on all permutation of {Si, Ei} and optimize or I miss any important algorithm I should know? Or even I am over-thinking....

Answer 1

If I understand you correctly, you want to find the tree of minimal weight in the graph that contains all the vertices of E and at least one vertex from S.

The problem is called general Steiner tree, and it is NP-hard. So the best you can probably hope for is an exponential-time algorithm or some kind of approximation (the minimum spanning tree of the whole graph comes to mind, maybe after removing some unneeded subtrees).

There is a simple DP solution that works in O(2^n * (n + m)): Let f(S) be the cost of the minimum tree in the graph that spans all the nodes in S. It can be shown that there is such a tree T such that the weight of T \ {x} is f(S \ {x}) for some x, so the transition can be done in O(n + m).