How would you modify BFS to find the shortest path from A to B, given that the graph is very large?

Question

What I mean by "very large graph" is that each vertex has 1000 adjacent vertices, but if you go to see the final solution the distance from A to B was just 6 (say).

In such a situation, using the basic BFS algorithm would be wasteful as it puts all the 1000 of A's adjacent vertices and then in the next round 1000 for each of these and so on..by time I reach B I would have considered 1000^6 vertices..

Any Idea how to optimize? Or rather is there a way?

Answer 1

One easy thing to do is to work from both directions:

At each step, do this:

• get new neighbors of nbrsA looking for B, if not found set nbrsA = new neighbors
• get new neighbors of nbrsB looking for A, if not found set nbrsB = new neighbors
• compare nbrsA and nbrsB

If the graph is big but highly connected, then you'll save a fair amount of space this way, but it does cost some extra time to compare the sets of neighbors.

Answer 2

You could change the BFS to use Dijkstras algorithm. BFS and Dijkstras are related in certain ways and so this modification should be acceptable. And since this was a phone screen there are a lot of chances they wanted you to see the relationship there.