graphs.breadth_first_search_shortest_path_2

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

Attributes

demo_graph

Functions

bfs_shortest_path(→ list[str])

Find shortest path between start and goal nodes.

bfs_shortest_path_distance(→ int)

Find shortest path distance between start and target nodes.

Module Contents

graphs.breadth_first_search_shortest_path_2.bfs_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")
[]
graphs.breadth_first_search_shortest_path_2.bfs_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
graphs.breadth_first_search_shortest_path_2.demo_graph