onkarbartakke / bi-directional-search-algorithm-implementation-on-n-tile-problem Goto Github PK
View Code? Open in Web Editor NEWSearching a graph is quite famous problem and have a lot of practical use. We have already discussed here how to search for a goal vertex starting from a source vertex using BFS. In normal graph search using BFS/DFS we begin our search in one direction usually from source vertex toward the goal vertex, but what if we start search from both direction simultaneously. Bidirectional search is a graph search algorithm which find smallest path from source to goal vertex. It runs two simultaneous search โ Forward search from source/initial vertex toward goal vertex Backward search from goal/target vertex toward source vertex Bidirectional search replaces single search graph(which is likely to grow exponentially) with two smaller sub graphs โ one starting from initial vertex and other starting from goal vertex. The search terminates when two graphs intersect.