overview

The Bellman-Ford algorithm is an algorithm used to find the shortest path from one vertex to the other vertices in a weighted graph. Same problem, but Bellman-Ford algorithm is slower than Dijsktra algorithm but more versatile in that it can work on graphs with negative weighted edges . The algorithm was first proposed by Alfonso Shimbel (1955), but named after Richard Bellman and Lester Ford Jr. The two published the algorithm in 1958 and 1956, respectively.

Technical

Question

Given the following graph:

Find the shortest path between vertex 1 and the rest of the vertices in the graph.

If the graph has negative weight edges, the implementation of the classic Dijkstra shortest path algorithm will fail. The improved implementation will help Dijkstra’s algorithm to overcome this problem. However, when the graph has negative cycles, this improved implementation also cannot be used because the algorithm will perform an infinite loop.

The Bellman Ford algorithm solves this problem. The main idea is very simple that is

Algorithm description

We consider an example with a graph with an upper direction (assuming the paths are one-way, only going from the vertex with the lower sequence number to the vertex with the higher order number, the red number next to each vertex is the length of the path. shortest path from root to that vertex, and root vertex is vertex 1).

Initialization:

Performing the first traversal, we can update the shortest path through edges (1, 2); (1, 3); (1, 4):

Similar to the 2nd pass, edges (2, 5) and (3, 4) are optimal edges:

With the 3rd pass, only the edge (4, 5) improves the optimal path:

By the 4th traverse, we see that there are no longer any edges that can optimize any shortest path. At this point, we can completely stop the traversal (because surely no more optimal edges means there are no negative cycles in the graph).

Pseudo code :

Setting

Code :

• Best case time complexity:
  O (E ) O(|E|)$O(E|)\_$
• Average time complexity:
  O (E .DRAW ) O(|E|.|V|)$O(E|.|V|)\_$
• Worst case time complexity:
  O (E .DRAW ) O(|E|.|V|)$O(E|.|V|)\_$

Algorithm application

A distributed variant of the Bellman-Ford algorithm used in distance vector routing protocols, such as the Routing Information Protocol (RIP). This is the distributed variant because it involves network nodes (routers) in an automated system, i.e. a set of IP networks owned by an Internet service provider. (ISPs).

The algorithm consists of the following steps:

• Each node calculates the distance between it and all other nodes in the automated system and stores this information in a table.
• Each node sends its information table to all neighboring nodes.
• When a node receives information tables from neighboring nodes, it computes the shortest routes to all other nodes and updates its own table of information.

The main disadvantages of the Bellman-Ford algorithm in this configuration are:

• Doesn’t scale well.
• Network topology changes are not recorded as quickly as updates are propagated node-by-node.
• Counting to infinity (if a broken link or broken network node causes a node to be separated from a set of other nodes, these nodes will continue to estimate the distance to that node and increase the calculated value, in then circular routing is also possible).

summary

References

1. Algorithms and Programming – Teacher Le Minh Hoang
2. cp-algorithms.com
3. Handbook Competitive Programming – Antti Laaksonen
4. Competitve programming 3 – Steven Halim, Felix Halim
5. https://sites.google.com/site/kc97ble/algorithm-graph/fordbellmanqueue-cpp