Bellman-Ford Algorithm

The Bellman Ford algorithm is another shortest path algorithm. Unlike Dijkstra's algorithm, though, this algorithm can handle edges with negative weights and detect negative cycles in a graph. Negative cycles are important because in a graph with negative cycles, there is no shortest path to some nodes since a negative cycle can be iterated an infinite number of times.

The algorithm works by initially setting the distance from the source node to all other nodes to be infinity. The distance to the source is then updated to be 0 since we are already there.
Next we proceed through each edge (u, v) and check the condition that if the distance to u plus the weight of the edge (u, v) is less than the distance to the node v, then we have just found a shorter route to v.

This condition on the edges only needs to be checked at most |V| times for each edge since any path will contain at most |V| edges, which means that the distance of a node can be updated at most |V| times.

If after |V| times there is still a node whose weight can be updated, it signifies the existence of a negative weight cycle and the Bellman-Ford will show that this cycle exists, but will be unable to find shortest paths in this problem as shortest paths no longer exist.


Show Work?
your browser does not support the canvas tag

 

Recent Updates

  • 07-16-2014 Hierarchical Clustering
  • 07-02-2014 Introduction to JavaScript Programming
  • 06-16-2014 Simple Linear Regression
  • 05-08-2014 Learning About Truth Tables
  • 03-29-2014 Introduction to Python Programming
  • 03-10-2014 Probability: Sample Spaces
  • 02-21-2014 Dots and Boxes Game
  • 02-04-2014 K Means Clustering for 2013 NFL Stats
  • 01-22-2014 Nim Games
  • 12-14-2013 The Corral Puzzle
  • 11-10-2013 Interactive Tutorial of Kruskal's Algorithm
  • 11-10-2013 Assembly Line Scheduling
  • 10-23-2013 Interactive Tutorial of Prim's Algorithm
  • 10-20-2013 Interactive Tutorial of Dijkstra's Algorithm
  • 10-13-2013 A JavaScript Implentation of MapReduce's WordCount
  • 10-12-2013 The Assignment Problem
  • 08-29-2013 Polynomial Arithmetic
  • 08-20-2013 Hidden Markov Models: The Baum-Welch Algorithm
  • 08-18-2013 Hidden Markov Models: The Viterbi Algorithm
  • 08-15-2013 Hidden Markov Models: The Backwards Algorithm