Algorithm for shortest path to cover all the routes

This is a variation of a question I came across in one of the mock-interview videos.

Assume there's a bunch of routes ex: [rome->dallas, dallas->rome, london->paris, paris->frankfurt, london->dallas, frankfurt->rome] etc. Now I want to add a new location to this route ex: delhi. The question is to to find the minimum no. of connections i need to build such that I can cover all the above places from Delhi ?

My solution is:

  1. Build a graph and get the list of strongly connected components in that graph.
  2. Add an edge from this new location to at-least one node of every component in the list of SCC's. Since every node is connected to every other in a SCC, adding an edge to any one of the nodes should work.

Does this solution make sense ? I'm unable to come up with a way to prove that this can work in every situation. Is there any drawbacks of this solution. Please share your inputs/comments.

Read more here:

Content Attribution

This content was originally published by vinit at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: