Bellman-Ford Algorithm: Shortest Path Finding with Negative Weights

Bellman-Ford is a shortest path algorithm used to find the shortest path between a source node and all other nodes in a weighted directed graph. It can handle graphs with negative edge weights, unlike Dijkstra's algorithm.

The algorithm works by iteratively relaxing the edges in the graph. In each iteration, it considers all edges and updates the distance of each node if a shorter path is found. The algorithm repeats this process for a total of V-1 iterations, where V is the number of nodes in the graph.

Initially, all nodes except the source node are assigned a distance of infinity. The distance of the source node is set to 0. Then, in each iteration, the algorithm checks all edges and updates the distance of each node if a shorter path is found. After V-1 iterations, the algorithm has found the shortest path from the source node to all other nodes, assuming no negative cycles exist.

If a negative cycle is present in the graph, the algorithm can detect it. In the Vth iteration, if any distance is updated, it means a negative cycle is present. This is because in a negative cycle, the distance to a node can be continuously reduced by going around the cycle repeatedly.

Overall, the Bellman-Ford algorithm has a time complexity of O(V * E), where V is the number of nodes and E is the number of edges in the graph.