Bellman Ford - Eishaaya/GMRDataStructuresTest GitHub Wiki

What is a Cycle?

In graph theory, a path that starts from a given vertex and ends at the same vertex is called a cycle. So, a cycle is a path where the first and last vertex are the only repeated vertices. For example, with the graph below a possible cycle would be the path that goes B->F->E->B, because, the first and last vertex are repeated. There is one cycle in the graph below, but 3 possible paths that the cycle could follow.

Bellman Ford algorithm

The Bellman-Ford algorithm is a pathfinding algorithm that can pathfind in graphs with negative-weight edges, which makes it more versatile than Dijkstra's algorithm. It is also capable of detecting if a graph contains a negative weight cycle. A negative weight cycle is a cycle where the sum of all the edge distances in the path add up to a negative number. If a negative cycle exists in a graph, then shortest paths between some pairs of vertices do not exist since any path between them could be made shorter by taking a detour to the negative cycle and going around the cycle a large number of times.

We are going to use the algorithm to detect a negative cycle with in our directed graph (it is going to be a predicate). The information that we need to know for each vertex is:

  • The known cumulative distance from the start vertex.
  • The founder vertex.

These extra variables can be stored in the vertex class or in separate data structures as part of the function. The steps of the algorithm are as follows:

  1. Initialize all the vertices by setting their known distance to ∞, and setting their founder to null.
  2. Assign the start vertex's known distance to 0 (since it is a distance of 0 from the start vertex!)
  3. "Relax" all of the edges in the graph, which means calculate the tentative distance of the end vertex and replace the end vertex's current distance with the newly-calculated tentative distance if the new distance is lower. Also update the end vertex's founder if necessary. Run this step a total of |V| - 1 times where V is the number of vertices.
    • After |V| - 1 iterations, the known distance of each vertex is equal to its true distance from the start vertex if and only if that vertex is reachable from the start vertex and there are no negative cycles.
  4. Relax all of the edges one more time. If any relaxation results with a tentative distance being better than a vertex's current distance, then we've found a negative cycle.

Assignments to be done with Bellman Ford algorithm

  • Implement Bellman Ford algorithm and test to see if it can detect negative weight cycle.
    • Print out the path of a graph traversal where the algorithm does not get stuck in a negative weight cycle.

References

<-- Previous | Next -->