aaryahjolia / dsa_competitive-coding

A repository to learn deep competitive coding algorithms along with DSA.
MIT License
96 stars 122 forks source link

[GSSoC'23] Add Bellman Ford Algorithm #508

Open bhartik021 opened 1 year ago

bhartik021 commented 1 year ago

This commit introduces the implementation of the Bellman-Ford algorithm, a widely used shortest path algorithm in graph theory. The algorithm efficiently calculates the shortest paths from a source vertex to all other vertices in a weighted directed graph, even in the presence of negative weight edges.

The Bellman-Ford algorithm operates by iteratively relaxing edges, gradually improving the shortest path estimates until reaching the optimal solution. This implementation employs a dynamic programming approach, where an array of distances is maintained, and each iteration updates the distances based on the relaxation of edges.

The algorithm has been implemented in the designated file, [file name], which includes the necessary functions and data structures for its execution. The implementation adheres to the algorithm's time complexity of O(|V||E|), where |V| represents the number of vertices and |E| represents the number of edges in the graph.

To ensure accuracy and efficiency, appropriate test cases have been added, covering various scenarios such as graphs with negative weight cycles, disconnected graphs, and graphs with different edge weights. These tests validate the correctness of the implementation and serve as a benchmark for future modifications or optimizations.

The addition of the Bellman-Ford algorithm provides a powerful tool for solving shortest path problems in graphs, expanding the range of algorithms available in the project. Its inclusion strengthens the project's capabilities and offers new opportunities for graph analysis and optimization.

bhartik021 commented 1 year ago

Please assign this issue to me under GSSoC'23