Route Finder Using Bi-Directional BFS/DFS

Use Bi-directional BFS/DFS to solve a navigation problem.
Problem Statement: Represent a city map as a graph where intersections are nodes and roads are edges. Find the shortest path between two locations.

1. Bi-Directional BFS/DFS
Dr Hitesh Mohapatra
AssociateProfessor
AI-LAB : Assignment 3

2. Assignment 3: Route Finder Using Bi-
Directional BFS/DFS
Objective:UseBi-directionalBFS/DFStosolveanavigationproblem.
ProblemStatement:Representacitymapasagraphwhereintersectionsare
nodesandroadsareedges.Findtheshortestpathbetweentwolocations.
Tasks:
•ImplementBi-directionalBFStominimizethenumberofnodesexplored.
•ComparetheperformanceofBi-directionalBFSwithstandardBFSand
DFS.
•Visualizethesearchprocess(e.g.,usingalibrarylikenetworkxinPython).

3. What is Bi-Directional BFS?
•Insteadofsearchingfromjust
thesourcenode,Bi-Directional
BFSsearchesfromboththe
startandtarget.
•Thesearchstopswhenthetwo
searchesmeetinthemiddle.
•Significantlyreduces the
numberofnodesexplored.

4. Bi-Directional BFS Implementation:
Bi-directionalBFSworksbysimultaneouslysearchingfromboththesource
andthetargetnodes.Thesearchmeetsinthemiddle,potentiallyreducing
thenumberofexplorednodesandspeedingupthesearch.Thisis
particularlyeffectiveforlargegraphs.
StepsforBi-DirectionalBFS:
1.Initializetwoqueues:onestartingfromthesourceandtheotherfrom
thetarget.
2.Expandnodesalternatelyfrombothends,markingvisitednodesforboth
forwardandbackwardsearches.
3.Ifanodeisvisitedbybothsearches,thealgorithmstops,andthepathis
reconstructed.

5. Process
It runs two simultaneous search –
1.Forward search from source/initial vertex toward goal vertex
2.Backward search from goal/target vertex toward source
vertex

6. Example
Suppose we want to find if
there exists a path from vertex 0
to vertex 14. Here we can
execute two searches, one from
vertex 0 and other from vertex
14. When both forward and
backward search meet at vertex
7, we know that we have found
a path from node 0 to 14 and
search can be terminated now.
We can clearly see that we
have successfully avoided
unnecessary exploration.

7. When to use bidirectional approach?
We can consider bidirectional approach when-
1.Both initial and goal states are unique and completely
defined.
2.The branching factor is exactly the same in both directions.

8. Algorithm
while sq != empty and tq != empty
perform next iteration for sq
perform next iteration for tq
save the root of a leaf node in the root array
if we have visited the node of intersection
save it
break
using node of intersection and root node, find the path

9. Why bidirectional approach?

10. Comparing BFS and bi-directional BFS.

11. https://github.com/hm18818/AI-with-Python/blob/main/Bi-Directional%20BFS