Algorithm for shortest path to cover all the routes

user_2882621 0
Viewed 70

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.

graph algorithm
1 Answers

Thanks to @Henry, the tricky part of the question is to understand that either finding weakly or even strongly-connected components and just adding one-route each to such components wont do.

A good example as @Henry pointed out is: L->P exists; adding Delhi, just needs adding one route to L

For the argument against weakly connected components, consider L->P<-C; we need atleast two routes but there's only 1 weakly connected component

My approach:

  1. Sort all cities based on their number of incoming-routes (lowest first) -> Lets call this list as in_degree_sorted_cities

  2. Pop element from this list; and:

    a. Add a new route to this city;

    b. Do a BFS and remove all the reachable cities from the in_degree_sorted_cities list.

I would consider this approach:

  1. Find all the connected-components in the graph.
  2. To access all the cities, you just need to add new routes (to and fro route to any one city in each connected-component) to each of these connected-sub-graphs.

Connected-component

Any two nodes in a connected-component can be reached from one another either by direct-route or indirect.

Proof by contradiction:

Since you are looking to add minimum number of connections, I think the proof is straightforward by contraction.

For example if u remove any one of those connections to a connected-component, you can no longer access it.

user_102084810
Related