The Bellman-Ford code given in lecture notes will report “Negative cycle detected” if there is a negative-weight cycle reachable from the start vertex. Modify the code so that, in such cases, it returns a negative-weight cycle, rather than just reporting that one exists.
Please submit a source file bf_cycle.py on Moodle. It should implement a function
bf(g, s)
# Return either (minweights,None) or (None,badcycle)
# -- badcycle is a negative weight cycle reachable from s, [v1, v2, ..., v1]
# -- minweight is a dictionary of mininum weights to each vertex, {v: minweight to v, ...}The graph g is stored as an adjacency dictionary, for
example g = {'a':{'b':3,'c':-2}, b:{}, 'c':{'a':-1}}. It
has a key for every vertex, and the corresponding value is a dictionary
of that vertex’s neighbours with the corresponding edge weight.