How Bellman-Ford Works

After V-1 relaxation passes, the distance array holds shortest paths for any graph without a negative cycle. The proof is the edge-count invariant: after k passes, every shortest path using at most k edges is correct, and no acyclic shortest path needs more than V-1 edges. If any edge still improves a distance after V-1 passes, the only explanation is a negative cycle reachable from the source. check_negative_cycle runs exactly one more pass over every edge on line 13. The unpacking on line 14 pulls "src", "dst", and "weight" from each dict in one expression. The distance[u] != float("inf") guard on line 15 skips unreachable vertices, because infinity plus any finite weight is still infinity and no cycle through an unreachable vertex matters.

The signature takes four arguments because the graph format here is not an adjacency dict but a flat list of edge dicts. Each dict has keys "src", "dst", and "weight". The explicit vertex_count and edge_count parameters are required because the flat edge list does not expose the vertex count, and the outer loop iterates exactly vertex_count - 1 times. The first doctest constructs a four-vertex graph with one negative edge (weight -10 from vertex 2 to vertex 1) and expects distances [0.0, -2.0, 8.0, 5.0] from source 0. The second doctest adds one more edge that creates a negative cycle and expects the Exception: Negative cycle found traceback. The Traceback (most recent call last): ... pattern on lines 32 through 34 is the standard doctest format for testing that an exception is raised.

Line 36 initializes every vertex's distance to positive infinity, signaling that no path is yet known. Line 37 sets the source to 0.0, matching the list[float] return type. The outer loop on line 39 runs exactly vertex_count - 1 times: the maximum edge count on any shortest acyclic path. The inner loop on line 40 walks every edge. Line 41 extracts src, dst, and weight from the current edge dict using the same generator pattern as check_negative_cycle. Line 43 is the relaxation test: if vertex u is reachable and the path through it is cheaper than the current distance to v, line 44 updates distance[v]. The absence of a priority queue or visited set is what produces O(VE) rather than Dijkstra's O((V + E) log V).

Lines 46 through 50 are the completion contract: run the V-th pass via check_negative_cycle, raise if a cycle is found, return the distance list if not. Raising an exception rather than returning a sentinel value is the contribution guide's preferred pattern for conditions that invalidate the result. A caller who catches this exception knows the graph is malformed for the purpose of single-source shortest paths. A caller who does not catch it gets a clear stack trace rather than a silently wrong distance table. The return type list[float] uses float rather than int because the initialization uses float("inf") and Python's type system propagates that to the entries that remain infinite when a vertex is unreachable from the source.

The __main__ block follows the same pattern as graphs/dijkstra.py: run doctest.testmod() first so any regression in the docstring examples surfaces immediately on direct invocation, then drop into an interactive session. The interactive session builds the graph edge by edge from stdin. Lines 65 through 67 read space-separated source, destination, and weight for each edge and pack them into the dict format the algorithm expects. The loop on line 63 prompts the user for each edge with a human-readable label. Line 69 asks for the source vertex after all edges are entered, then calls bellman_ford and passes the result to print_distance. Notice the print_distance call on line 73 passes 0 as the source label rather than the actual source variable, which is a minor inconsistency in the file: the displayed header will always read "Shortest Distance from vertex 0" regardless of what source was entered.