Understanding the Bellman-Ford algorithm

The Bellman-Ford algorithm is a single-source shortest path-finding algorithm that can solve this problem for graphs with negative edge weights. Dijkstra's algorithm fails on graphs with negative edge weights because it assumes the first time we reach a node will always be via the shortest path. This assumption is valid for graphs with non-negative edge weights but not for those with negative edge weights. The Bellman-Ford algorithm overcomes this by calculating the shortest path for each node incrementally over multiple iterations and considering every path from the source to that node.

Algorithm

The Bellman-Ford algorithm finds the shortest distance from the source to all nodes by starting from a base condition and relaxing the distance values of all nodes until it is no longer possible.

We start by creating a distance map to store the currently known shortest distance of a node and initialize it to infinite for each node and 0 for the source node, which acts as the base condition for the algorithm. We then iterate through all the edges of the graph and, for each edge, check if it reduces the distance value of its destination node. For example, for an edge from node u to node v having a weight w, we check if distance[u] + w < distance[v] and update the distance map if the new distance is less than what was stored. This process is called relaxing the edge from the node u to node v.

After relaxing all the graph's edges, the distance map may have been modified for a few nodes. Consider that the node u is adjacent to nodes a, b and c while node v had nodes x, y and z as adjacent nodes. The distance value of nodes a, b and c may have been reduced, which could reduce the distance for the node u. Similarly, since the distance of the node v might have been reduced, this could reduce the distance value of the nodes x, y, and z.