bellman_ford.py

class Graph():
    def __init__(self, g):
        self.g = g

    def bellman_ford(self, source):
        dists = { vert: float("inf") for vert in self.g }
        paths = { vert: None for vert in self.g }
        dists[source] = 0

        for i in range(len(self.g) - 1):
            for u in self.g:
                for v in self.g[u]:
                    if dists[v] > dists[u] + self.g[u][v]:
                        dists[v] = dists[u] + self.g[u][v]
                        paths[v] = u

        for u in self.g:
            for v in self.g[u]:
                if dists[v] > dists[u] + self.g[u][v]: return False

        return dists, paths

g = Graph({
        'a': {'b': -1, 'c':  4},
        'b': {'c':  3, 'd':  2, 'e':  2},
        'c': {},
        'd': {'b':  1, 'c':  5},
        'e': {'d': -3}
        })
print(g.bellman_ford('a'))
# ({'a': 0, 'b': -1, 'c': 2, 'd': -2, 'e': 1}, {'a': None, 'b': 'a', 'c': 'b', 'd': 'e', 'e': 'b'})