Example sheet 4. Breadth-first search can be used to
find a shortest path between a pair of vertices. Modify the standard
bfs algorithm so that it returns all shortest
paths.
Please submit a source file that implements a function
# 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
shortest_paths(g, s, 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.
Submission filename: ex4.py or ex4.ipynb
You may submit either a plain .py source code file, or a .ipynb notebook. If you submit a notebook and it has code that you don’t want the tester to run, create a markdown cell that starts “# test” and the tester will ignore everything that follows.