The Bellman-Ford(-Moore) Algorithm
The Bellman-Ford(-Moore) algorithm is an alternative to Dijkstra’s algorithm for finding shortest paths in graphs.
The basic idea is that we find the shortest paths from a start node to other nodes by using 1, 2, $n$ links, where $n$ is the number of nodes in the graph.
So we start with shortest paths that have only one link, then with two links, and so on.
We will use the following function to read weighted graphs from files containing one line per edge.
This is familiar, it is the same that we used with Dijkstra’s algorithm.
def read_graph(filename, directed=False):
graph = {}
with open(filename) as input_file:
for line in input_file:
parts = line.split()
if len(parts) != 3:
continue # not a valid line, ignore
[n1, n2, w] = [ int (x) for x in parts ]
if n1 not in graph:
graph[n1] = []
if n2 not in graph:
graph[n2] = []
graph[n1].append((n2, w))
if not directed:
graph[n2].append((n1, w))
return graph
As a first example we will use the traffic grid graph again.
The Bellman-Ford(-Moore) Algorithm
The Bellman-Ford(-Moore) algorithm is an alternative to Dijkstra’s algorithm for finding shortest paths in graphs.
The basic idea is that we find the shortest paths from a start node to other nodes by using 1, 2, $n$ links, where $n$ is the number of nodes in the graph.
So we start with shortest paths that have only one link, then with two links, and so on.
We will use the following function to read weighted graphs from files containing one line per edge.
This is familiar, it is the same that we used with Dijkstra’s algorithm.
def read_graph(filename, directed=False):
graph = {}
with open(filename) as input_file:
for line in input_file:
parts = line.split()
if len(parts) != 3:
continue # not a valid line, ignore
[n1, n2, w] = [ int (x) for x in parts ]
if n1 not in graph:
graph[n1] = []
if n2 not in graph:
graph[n2] = []
graph[n1].append((n2, w))
if not directed:
graph[n2].append((n1, w))
return graph
As a first example we will use the traffic grid graph again.