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

breadth-first-searchgraphpathsearch

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?

Best Answer

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 Solutions

Python – How to get an absolute file path in Python

>>> import os
>>> os.path.abspath("mydir/myfile.txt")
'C:/example/cwd/mydir/myfile.txt'

Also works if it is already an absolute path:

>>> import os
>>> os.path.abspath("C:/example/cwd/mydir/myfile.txt")
'C:/example/cwd/mydir/myfile.txt'

Python – How to get the filename without the extension from a path in Python

Getting the name of the file without the extension:

import os
print(os.path.splitext("/path/to/some/file.txt")[0])

Prints:

/path/to/some/file

Documentation for os.path.splitext.

Important Note: If the filename has multiple dots, only the extension after the last one is removed. For example:

import os
print(os.path.splitext("/path/to/some/file.txt.zip.asc")[0])

Prints:

/path/to/some/file.txt.zip

See other answers below if you need to handle that case.

Best Answer

Related Solutions

Python – How to get an absolute file path in Python

Python – How to get the filename without the extension from a path in Python

Related Topic