Bellman Ford

In CS 3510 we recently learned about the Bellman Ford algorithm. It’s used for DAG’s (Directed Acyclic Graphs) that have negative edge weights in particular. The Bellman Ford algorithm is a dynamic programming algorithm that finds the shortest path from a source node to all other nodes in a graph. It is a generalization of Dijkstra’s algorithm, which only works on graphs with non-negative edge weights. The Bellman Ford algorithm can be used to find the shortest path in a graph with negative edge weights, but it is not guaranteed to find the shortest path in a graph with a negative cycle. The algorithm works by relaxing the edges of the graph in a topological order (also confusingly called linearization in CS3510).

Algorithm

The Bellman Ford algorithm works by relaxing the edges of the graph in a topological order. The algorithm starts by initializing the distance of the source node to 0 and all other nodes to infinity. Then, it relaxes the edges of the graph in a topological order. The algorithm then checks if there are any negative cycles in the graph. If there are, then the algorithm returns an error. If there are no negative cycles, then the algorithm returns the distances of all nodes from the source node.

I’m a more visual learner, so to illustrate the algorithm at work, I created a visualization in javascript that shows how the edges’ costs are calculated. The visualization generates a random graph with random edge weights every time.

Visualization

0