How to use Dijkstra's Algorithm for finding shortest path with vertex constraint

Question

I have been stuck on this problem for two days now and still no progress. Basically the problem is as follows: Given an undirected simple weighted and connected graph, we have to find the shortest walk from a given source to a given destination while visiting at least one vertex from a given set, A and at least one vertex from the set B with the added constraint that the vertex from set B should always come after visiting the vertex from set A. Set A and B are disjoint and there can be vertices in the graph which neither belong to A nor B. There is a single source and destination vertex.

I tried decomposing the shortest path into one which visits a vertex, v in A from source, then from v to another w in B and then from w to destination. This can be done using 3 passes of Dijkstra with different starting vertices respectively. But, I would have to choose the minimum such v resulting in O(VElog(V)) complexity where V = number of vertices and E = number of edges. I am terribly stuck on how to do this in O(E*log(V)), since the question asks so, i.e. using only O(1) Dijkstra runs. Can anybody please help me?

Edit: We can't construct a new graph or modify it as some people are suggesting to construct a level graph. I have to modify the Dijkstra routine somehow to solve this. Graph. Blue vertices are the set A, purple ones set B. Home is 0 and Destination is 8 In this graph(see link) for example, the shortest walk should be: 0 -> 1 -> 0 -> 3 -> 6 -> 7 -> 8 with total cost = 6

Answer 1

The easiest (to me) way to solve such problems is to separate graph vertices into "levels" (like stories in a building) and possibly replicate some vertices between more than one level.

In your case, there will be 5 levels, levels 1, 3 and 5 containing all vertices while level 2 only has A vertices and level 4 only has B. The start vertex is at level 1 and the end is at level 5. The original edges are replicated within each level and between adjacent levels.

Any path in the modified graph passes through an A vertex and after that through a B vertex, because any path must pass through all 5 levels in order.

This arrangement does not care if there are additional A and B vertices in any order, in addition to the mandatory pair in the required order (so x-x-x-A-B-A-B-x-x-x is allowed). If you need to exclude those, remove all B vertices from levels 1 and 3, and all A vertices from levels 3 and 5.

Answer 2

As @n.'pronouns' m. pointed out, we can solve this problem by graph layering. Specifically for my case, just add a new source vertex and add edges from this source vertex to all the edges of vertices belonging to A of original graph. The weight of these edges would be the same as the shortest path found from original source to this vertex in original graph. Similarly, you add a new destination vertex and add edges from all B vertices to this new vertex and the weight of the edge is again the shortest path from the B vertex to original destination vertex in original graph. Now if you run Dijkstra from new source to new destination, you see that atleast one A vertex would be visited before B vertex finally ending at new destination. This path is indeed the shortest path.