Implement the Bellman-Ford algorithm to find the shortest paths from a source vertex in a weighted graph with possible negative edges.
Implement the function `bellman_ford(n, edges, source)` that computes the shortest distances from a given source vertex to all other vertices in a directed weighted graph.
The graph has `n` vertices numbered from 0 to n-1. The edges are provided as a list of tuples `(u, v, w)` representing a directed edge from vertex `u` to vertex `v` with weight `w` (can be negative). There are no self-loops, but there may be multiple edges between the same pair of vertices. The graph may contain negative-weight cycles, but no negative cycles reachable from the source (ensuring well-defined shortest paths).
The function should return a list of `n` integers where the `i`-th element is the shortest distance from `source` to vertex `i`. If a vertex is unreachable from the source, the distance should be `None` (Python's `None`), not infinity. The tests expect `None` for unreachable vertices.
The approach must use the Bellman-Ford algorithm, which relaxes all edges `n-1` times. You may assume that the graph contains no negative cycles reachable from the source.
For example, if `n=4`, `edges=[(0,1,2),(1,2,-1),(0,3,1),(3,2,3)]`, and `source=0`, the distances are `[0,2,1,1]` because 0->1 (2), 0->3 (1), and 0->1->2 (2-1=1).
Implement the function with the exact signature above. Do not print anything. The tests will call this function directly.
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ len(edges) ≤ 1000
- Each edge weight is an integer between -1000 and 1000.
- Vertices are numbered 0 to n-1.
- The source is a valid vertex index.
- The graph contains no negative cycles reachable from the source.
Complexity expectation: O(n*m) time, O(n) extra space, where m is the number of edges.
Example
>>> bellman_ford(4, [(0,1,2),(1,2,-1),(0,3,1),(3,2,3)], 0)
[0, 2, 1, 1]
>>> bellman_ford(3, [(0,1,5)], 2)
[None, None, 0]
>>> bellman_ford(2, [(0,1,-2)], 0)
[0, -2]
>>> bellman_ford(1, [], 0)
[0]
30 points
~30 min