Bellman-Ford Algorithm

I just finished a script which executes the Bellman-Ford Algorithm on a randomly generated directed graph (possibly with negative arcs). It can be accessed here.

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.


Similar Posts:

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.