CODEWITHSUNDEEP
algorithmgraph-theorydijkstra
NotSure
NotSure

Reputation: 681

Find the shortest path in an graph containing at most two red edges

The question is : enter image description here

I know that we should duplicate the graph into G1 and G2 and probably use Dijstra's algorithm. I am not sure how i should connect G1 and G2 in a way that i will get the right solution for this question.

Upvotes: 2

Views: 1956

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59303

You almost have the answer:

  1. Make two more copies of the graph, so you have G, G1, and G2.
  2. Remove the red edges from G2, change every red edge in G1 to point to the corresponding vertex in G2 instead of G1, and change every red edge in G to point to the corresponding vertex in G1.
  3. Now, every path that has 2 red edges ends up in G2, and ALL paths that have 2 red edges end up in G2. Similarly all paths that have 1 red edge end up in G1. Use Dijkstra's algorithm to find the shortest paths from s in G to all the vertexes in G, G1, and G2.
  4. For each vertex in G, look at the paths to the corresponding vertices in G, G1 and G2, take the shortest one, and translate it back to the original graph. (because paths with less than 2 red edges are also acceptable)

Upvotes: 6

Related Questions