Negative weights

Bellman-Ford handles negative weights.

Bellman-Ford is a single-source shortest path algorithm that supports negative edge weights. It does what Dijkstra cannot.

The algorithm relaxes all edges n-1 times. This relies on the fact that the longest path has at most n-1 edges.

Edge list

Bellman-Ford works with an edge list rather than a graph object. Each edge is a (u, v, w) triple: from u to v with weight w.

This representation lets the algorithm traverse all edges one by one. Complexity is O(n·m); m is the edge count.

Write init_edges(). Return the edge list. Print it with print(init_edges()).

Show example solution

def init_edges():
    # Return edge list
    return [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
print(init_edges())

Edge definition

edges = [(0, 1, ____)]

Show answer

edges = [(0, 1, 4)]