Dijkstra breaks when edge weights can be negative. Bellman-Ford does not: it simply relaxes every edge repeatedly.
Implement bellman_ford(n, edges, source). The graph has n vertices numbered 0..n-1. edges is a list of directed weighted tuples (u, v, w) meaning an edge from u to v with weight w (possibly negative). Assume there is no negative-weight cycle.
Return a list dist of length n where dist[i] is the shortest distance from source to i, using float('inf') for vertices that cannot be reached.
Algorithm:
After n - 1 full passes every shortest path (which uses at most n - 1 edges) has settled.
def bellman_ford(n, edges, source):
"""Return shortest distances from source; float('inf') if unreachable."""
# TODO: init dist, then relax all edges n - 1 times.
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Dijkstra breaks when edge weights can be negative. Bellman-Ford does not: it simply relaxes every edge repeatedly.
Implement bellman_ford(n, edges, source). The graph has n vertices numbered 0..n-1. edges is a list of directed weighted tuples (u, v, w) meaning an edge from u to v with weight w (possibly negative). Assume there is no negative-weight cycle.
Return a list dist of length n where dist[i] is the shortest distance from source to i, using float('inf') for vertices that cannot be reached.
Algorithm:
After n - 1 full passes every shortest path (which uses at most n - 1 edges) has settled.
Press Run Tests or ⌘↩ to check your solution.