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

  • 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 Step by Step Tutorial of Kruskal's Algorithm
  • 11-10-2013 Assembly Line Scheduling
  • 10-23-2013 Step by Step Tutorial of Prim's Algorithm
  • 10-20-2013 Step by Step 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
  • 08-13-2013 Hidden Markov Models: The Forward Algorithm
  • 07-04-2013 Term Frequency Inverse Document Frequency
  • 06-04-2013 Covariance of Vectors
  • 05-21-2013 The Gram-Schmidt Process and Orthogonal Vectors
  • 05-13-2013 Permutation Problems
  • 05-13-2013 My Review of "The Golden Ticket: P, NP, and the Search for the Impossible"
  • 05-05-2013 Approximating the Set Cover Problem
  • 04-16-2013 What is a "Hard" Problem?
  • 03-29-2013 Knapsack Problems
  • 03-22-2013 Triangle Trigonometry
  • 03-12-2013 Sudoku Program Updates
  • 03-02-2013 The PageRank Algorithm
  • 02-27-2013 The Risk of Competition
  • 02-08-2013 Nonogram Puzzles
  • 02-04-2013 Geometric Sequences
  • 02-02-2013 Arithmetic Sequences
  • 01-20-2013 Learn to Solve Single Variable Linear Equations
  • 01-08-2013 Fraction Arithmetic
  • 11-24-2012 Learn About "the Other" Algebra
  • 10-06-2012 Shade The Cells Puzzle
  • 10-06-2012 Learn Duality in Linear Programming
  • 10-02-2012 Learning the Apriori Algorithm
  • 08-28-2012 Visualizing Huffman Coding Trees
  • 08-16-2012 Understanding Bayes' Theorem
  • 08-08-2012 Learn Math Through Set Relations
  • 07-24-2012 How Could You Possibly Love/Hate Math?
  • 07-08-2012 Learn About Binary Search Trees
  • 06-25-2012 Learning Math through Set Theory
  • 06-25-2012 Linear Search Algorithm
  • 06-25-2012 Examples of the Binary Search Algorithm
  • 06-25-2012 Queue Data Structure
  • 06-25-2012 Stack Data Structure
  • 06-11-2012 Sorting Algorithms (Take Two)
  • 04-30-2012 My Life (as a Number)
  • 04-22-2012 K-Means Clustering
  • 03-04-2012 The Simplex Method
  • 01-02-2012 New Years is a LEARNINGlover Thing!
  • 12-23-2011 My Sudoku Program
  • 12-13-2011 Sorting Algorithms
  • 12-10-2011 So You Want to Program? Lets Get Started!
  • 12-09-2011 What Can I Do to Help End the Recession?
  • 12-07-2011 The Degrees of Consciousness of a Black Nerd
  • 12-05-2011 User Generated Flash Cards
  • 10-16-2011 Text Summarization
  • 08-30-2011 Bellman-Ford Algorithm
  • 08-28-2011 Dijkstra's Algorithm
  • 08-25-2011 Kruskal's Algorithm
  • 08-24-2011 Prim's Algorithm
  • 08-23-2011 Gaussian Elimination
  • 08-23-2011 The Euclidean Algorithm
  • 08-23-2011 Sieve of Eratosthenes
  • 08-23-2011 The Cost of Learning
  • 08-23-2011 Examples Page
  • 08-23-2011 Flash Cards Page
  • 08-23-2011 Hello, World!