breadth_first_search_shortest_path_2.py

"""Breadth-first search shortest path implementations.
doctest:
python -m doctest -v bfs_shortest_path.py
Manual test:
python bfs_shortest_path.py
"""

demo_graph= {
"A": ["B", "C", "E"],
"B": ["A", "D", "E"],
"C": ["A", "F", "G"],
"D": ["B"],
"E": ["A", "B", "D"],
"F": ["C"],
"G": ["C"],
}


defbfs_shortest_path(graph: dict, start, goal) ->list[str]:
"""Find shortest path between `start` and `goal` nodes.
 Args:
 graph (dict): node/list of neighboring nodes key/value pairs.
 start: start node.
 goal: target node.
 Returns:
 Shortest path between `start` and `goal` nodes as a string of nodes.
 'Not found' string if no path found.
 Example:
 >>> bfs_shortest_path(demo_graph, "G", "D")
 ['G', 'C', 'A', 'B', 'D']
 >>> bfs_shortest_path(demo_graph, "G", "G")
 ['G']
 >>> bfs_shortest_path(demo_graph, "G", "Unknown")
 []
 """
# keep track of explored nodes
explored=set()
# keep track of all the paths to be checked
queue= [[start]]

# return path if start is goal
ifstart==goal:
return [start]

# keeps looping until all possible paths have been checked
whilequeue:
# pop the first path from the queue
path=queue.pop(0)
# get the last node from the path
node=path[-1]
ifnodenotinexplored:
neighbours=graph[node]
# go through all neighbour nodes, construct a new path and
# push it into the queue
forneighbourinneighbours:
new_path=list(path)
new_path.append(neighbour)
queue.append(new_path)
# return path if neighbour is goal
ifneighbour==goal:
returnnew_path

# mark node as explored
explored.add(node)

# in case there's no path between the 2 nodes
return []


defbfs_shortest_path_distance(graph: dict, start, target) ->int:
"""Find shortest path distance between `start` and `target` nodes.
 Args:
 graph: node/list of neighboring nodes key/value pairs.
 start: node to start search from.
 target: node to search for.
 Returns:
 Number of edges in shortest path between `start` and `target` nodes.
 -1 if no path exists.
 Example:
 >>> bfs_shortest_path_distance(demo_graph, "G", "D")
 4
 >>> bfs_shortest_path_distance(demo_graph, "A", "A")
 0
 >>> bfs_shortest_path_distance(demo_graph, "A", "Unknown")
 -1
 """
ifnotgraphorstartnotingraphortargetnotingraph:
return-1
ifstart==target:
return0
queue= [start]
visited=set(start)
# Keep tab on distances from `start` node.
dist= {start: 0, target: -1}
whilequeue:
node=queue.pop(0)
ifnode==target:
dist[target] = (
dist[node] ifdist[target] ==-1elsemin(dist[target], dist[node])
 )
foradjacentingraph[node]:
ifadjacentnotinvisited:
visited.add(adjacent)
queue.append(adjacent)
dist[adjacent] =dist[node] +1
returndist[target]


if__name__=="__main__":
print(bfs_shortest_path(demo_graph, "G", "D")) # returns ['G', 'C', 'A', 'B', 'D']
print(bfs_shortest_path_distance(demo_graph, "G", "D")) # returns 4