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

  • 08-10-2017 Floyd-Warshall Shortest Paths
  • 08-01-2017 Degree Centrality of a Graph
  • 06-03-2017 Tarjan's Strongly Connected Components Algorithm
  • 03-20-2017 Longest Common Subsequence
  • 10-27-2016 Independent Set Puzzles
  • 06-28-2016 Lets Learn About XOR Encryption
  • 06-15-2016 Discrete-time Markov Chains
  • 03-01-2016 Topological Sort
  • 01-21-2016 The RSA Algorithm
  • 11-20-2015 How To Take Notes in Math Class
  • 10-28-2015 The Depth-First-Search Algorithm
  • 10-28-2015 The Breadth-First-Search Algorithm
  • 09-23-2015 ID3 Algorithm Decision Trees
  • 07-08-2015 Clique Problem Puzzles
  • 06-25-2015 Unidirectional TSP Puzzles
  • 04-04-2015 Learn About Descriptive Statistics
  • 02-19-2015 Slope Formula
  • 01-15-2015 Interactive Midpoint Formula
  • 12-18-2014 Triangle Sum Puzzle
  • 12-02-2014 The Bridge Crossing Problem