The grid consists of following items as python list of lists
g = [
['1', '1', '1', '1', '1'],
['S', '1', 'X', '1', '1'],
['1', '1', '1', '1', '1'],
['X', '1', '1', 'E', '1'],
['1', '1', '1', '1', 'X']
]
S indicates the start, E indicates the end.
1 indicates the allowed paths, X are not allowed paths
A simple BFS traversal code is
def find_path_bfs(s, e, grid):
queue = list()
path = list()
queue.append(s)
while len(queue) > 0:
node = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
break
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if is_visited(item, v) is False:
queue.append(item)
return path
The algorithm, as far as I can tell is traversing correctly with the following output
[(1, 0), (1, 1), (2, 0), (0, 0), (2, 1), (0, 1), (2, 1), (0, 1), (2, 2), (3, 1), (0, 2), (2, 2), (3, 1), (0, 2), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 4), (3, 3)]
Each tuple in the list represents the indices for the node in the original graph.
How can rewrite my BFS code to return the shortest path instead of the entire traversal path followed to reach the destination node? I have spent hours to find answers on my own but so far I have been unsuccessful.
In order to get shortest path you should save path to current node in your queue too, so format of queue item will be:
(node, path_to_this_node)
Modified code:
def find_path_bfs(s, e, grid):
queue = [(s, [])] # start point, empty path
while len(queue) > 0:
node, path = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
return path
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if not is_visited(item, v):
queue.append((item, path[:]))
return None # no path found