There's a certain beauty to certain graph algorithms and how they incrementally process vertices and edges with each step. It reminds me of the child-like joy of filling in a coloring book.

Let me share that joy by dusting off my visualization skills from that one undergrad class I took and showing a step-by-step example of the Bellman-Ford algorithm in action.

# each vertex is named 0, 1, 2...
# PARAMS:
#   n: the number of vertices in the graph
#   edges: list of edges with their weight, each as [v1, v2, w]
#   src: the vertex we want to find distances from
def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(n - 1):
        for v1, v2, w in edges:
            if dist[v1] + w < dist[v2]:
                dist[v2] = dist[v1] + w

    return dist

The Bellman-Ford algorithm finds the shortest path from one vertex (the source) to all others in a weighted graph in O(V * E) time. It's a slower fallback for when Djiskstra's assumptions don't hold; Bellman-Ford works for negative edge weights, detection of cycles with negative total weight, and edge count limits.

After x runs of the outer loop, dist[v] represents the shortest distance from from v to src using at most x edges. Since the shortest path from any vertex to any other (barring negative cycles) happens in at most n-1 (number of vertices - 1) edges, we can run the outer loop that many times to get a final dist[].