Can someone describe the best possible step-by-step solution for this?
Let = (, ) be a weighted graph with a weight function : →ℝ+
Given a subset of vertices belonging to and vertex belonging to , describe an efficient algorithm that calculates for each vertex in the graph the weight of the lightest path from to itself that passes through at least one of 's vertices.
I'm not quite sure what the best approach might be.
You could clone the graph into '(',') by copying both vertices and edges (, ). Extend the combined graph with directed edges between and ' when is in , and give these extra edges a weight of 0. These 0-weight edges form bridges between and '.
Now find a path from to ' via the standard Dijkstra's algorithm. The only way to reach ' from is by traversing a "bridge"-edge that emits from a node in .
When you have the result, remove the "accents" from the vertices in the path, and remove the duplicate entry for the vertex that was the consequence of the 0-weight bridge edge on the path.
