How to get the path between 2 nodes using Breadth-First Search?

search graph path breadth-first-search
cleerline picture cleerline · Mar 1, 2011 · Viewed 12k times · Source

I am trying to find a path between two nodes in a graph, where the edges are unweighted.

I am using a Breadth First Search, which stops when it finds the target, in order to find the existence of a path, but I am not sure how to get the path itself.

I tried looking at the list of visited nodes, but this did not seem to help. I saw someone answer this question using prolog, but I am a C++ programmer.

I also looked at Dijkstras algorithm, but this seems like over kill, since a simple Breadth-first Search has got me almost the whole way.

How to get the path between 2 nodes using Breadth-First Search?

Answer

Thuy picture Thuy · Mar 1, 2011

In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.

Related questions

A* heuristic, overestimation/underestimation?

I am confused about the terms overestimation/underestimation. I perfectly get how A* algorithm works, but i am unsure of the effects of having a heuristic that overestimate or underestimate. Is overestimation when you take the square of the direct …

Read More
depth-first graph search that returns path to goal

I've been trying this all week and cannot, for the life of me, figure it out. I know that I need to have a helper function that will recurse and return pathSoFar. I can't seem to get my head around …

Read More
Why use Dijkstra's algorithm instead of Best (Cheapest) First Search?

From what I have read so far. The Best First Search seems faster in terms of finding the shortest path to the goal because Dijkstra's algorithm has to relax all the nodes as it traverses the graph. What makes Dijkstra's …

Read More