Directed Weighted Graph with required vertices

Question

Given: A directed, weighted graph G=(V, E), some of the vertices are red, some blue, and the rest white, weight Ti which is the maximum weight allowed to go from any vertex red vertex to any blue vertex.

Problem: Create an algorithm that finds a path from source node S, to target node T with least weight and which at some point goes from a red vertex to a blue vertex in at most Ti weight before reaching vertex T. The algorithm should have time complexity O(n^3)

Comments: I'm not sure how to get started on this, I figure it's some variation of Dijkstra's algorithm and I've seen some people talking about making copies of the graphs and connecting the copies but beyond that, I'm not sure what the setup of this algorithm would look like. Any help would be appreciated.

Answer 1

Indeed, you can use the copy-strategy as follows:

Copy the graph G to G' and to G". Label all vertices in G' as in G, but with the apostrophe. So there is an S' and a T' in G'. Similarly, S" and T" belong to G".

Let S be the start vertex, and T" be the target. As it stands now, G, G' and G" are disconnected. But add the following zero-weight, directed edges:

• Edges from each red vertex r in G, to its mirror r' in G'.
• Edges from each blue vertex b' in G', to its mirror b" in G".

So there are no paths from G" to G', nor from G' to G, nor from G" to G.

Now start a Dijkstra algorithm in S, with an additional data attribute for each entry in the priority queue: the weight that a path accumulated by edges in G' only. Let's call this w'. This w' plays no role in the priority of the queue. The total weight of a path determines the priority as is standard in Dijkstra's algorithm. The algorithm should not expand paths whereby w' would exceed Ti. Besides that specific limitation, all the rest of the algorithm can remain as in the standard Dijkstra algorithm.