Algorithms tick: bfs-all

Find All Shortest Paths

Breadth-first search can be used to find a shortest path between a pair of vertices. Modify the standard bfs_path algorithm so that it returns all shortest paths.

Please submit a source file bfs_all.py on Moodle. It should implement a function

shortest_paths(g, s, t)

# Find all shortest paths from s to t
# Return a list of paths, each path a list of vertices starting with s and ending with t

The graph g is stored as an adjacency dictionary, for example g = {0:{1,2}, 1:{}, 2:{1,0}}. It has a key for every vertex, and the corresponding value is the set of that vertex’s neighbours.

Note: the pseudocode in lecture notes uses syntax such as for v in g.vertices. For this tick, g is a plain Python dictionary, and so you can use dictionary methods instead — for v in g.keys().