CODEWITHSUNDEEP
algorithmdata-structuresgraphsocial-networking
Neeraj
Neeraj

Reputation: 1680

Algorithm to find if a node is reachable from another node

I have a large graph with millions of nodes. I want to check if node 'A' is reachable from node 'B' with less than 4 hops. If possible, I want the shortest path. Which is the best way (or algorithm) to solve this issue?

Upvotes: 2

Views: 3599

Answers (3)

amit
amit

Reputation: 178511

Note that if the graph is unweighted (as it seems in your question) - a simple and efficient BFS will be enough to find the shortest path from the source to the target.

Also, since you have a single source and a single target - you can apply bi-directional BFS, which is more efficient then BFS.

Algorithm idea: do a BFS search simultaneously from the source and the target: [BFS until depth 1 in both, until depth 2 in both, ....].
The algorithm will end when you find a vertex v, which is in both BFS's front.

Algorithm behavior: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source [explanation why it is better then BFS follows], and will surely provide an answer, if one exist.

why is it better then BFS from the source?
assume the distance between source to target is k, and the branch factor is B [every vertex has B edges].
BFS will open: 1 + B + B^2 + ... + B^k vertices.
bi-directional BFS will open: 2 + 2B^2 + 2B^3 + .. + 2B^(k/2) vertices.

for large B and k, the second is obviously much better the the first.

(*) The explanation of bi-directional search is taken from another answer I posted

Upvotes: 7

Vovanium
Vovanium

Reputation: 3898

If you need path less than 3 hops, then all possible paths are A (A=B), A-B (nodes are adjacent), A-X-B (X is a node adjacent to both ends). So there's no need in any complex algorithm. First, test for A=B, second, test that A and B are adjacent, and third, try to find X that is adjacent to both A and B (eg. intesection of endpoint adjacency sets).

Upvotes: 1

Jordan Lewis
Jordan Lewis

Reputation: 17948

The best algorithm for finding the shortest path between two nodes in a graph in which you have no extra information about how likely it is that one node is close to the target is Dijkstra's Algorithm. You can easily modify this algorithm to quit after 3 hops, to avoid wasting computation on results that you are not interested in.

If you do have some extra information about the likelihood that a given node is close to your target, you can use A* search, which uses a heuristic on a node's distance to its target to improve its runtime performance.

Upvotes: 3

Related Questions