I recently gave an interview at Dream11. I faced a graph question which states that we have a weighted undirected graph. We now have to travel from Node A to Node B in minimum possible cost, with conditions such that Node C and Node D should be in our path, also we can visit any node any number of times.
Can I know where I can practice similar problem? I solved the intermediate nodes part but visiting a node multiple times was not working.
Any suggestions are welcome.
We can use Dijkstra and can find shortest paths taking source as A, B and C.
Now, the paths can be
either
A ---> c --> D --> B
or
A ---> D ---> C ---> B
And we now ans would be
min(dist_from_A[C] + dist_from_C[D] + dist_from_D[B], dist_from_A[D] + dist_from_D[C] + dist_from_C[B])
And we have precalculated these values using Dijkstra . . .
Please Correct me if I’m wrong. . . Or if you’ve better approach, share it