This lesson's interactive features are locked, please to keep using them

Bellman-Ford Review

Let's consider the following reference implementation of the Bellman-Ford algorithm:

Graph = dict[str, dict[str, int]]


def bellman_ford(graph: Graph, src: str, dest: str) -> float:
    distances: dict[str, float] = {}
    for node in graph:
        if node == src:
            distances[node] = 0
        else:
            distances[node] = float("inf")

    for _ in range(len(graph) - 1):
        for node1 in graph:
            for node2 in graph[node1]:
                weight: int = graph[node1][node2]
                if distances[node1] + weight < distances[node2]:
                    distances[node2] = distances[node1] + weight

    for node1 in graph:
        for node2 in graph[node1]:
            weight: int = graph[node1][node2]
            if distances[node1] + weight < distances[node2]:
                raise Exception("negative cycle detected!")

    return distances[dest]