Day-24: Bellman-Ford Single Source Shortest Path ALgorithm

Day-24: Bellman-Ford Single Source Shortest Path ALgorithm

Bellman-Ford algorithm is used to calculate shortest paths from one vertex to every vertex on the graph.

However, it differs from Dijkstra in one thing: it works on negative edged graphs unlike Dijkstra.

The algorithm is rather straightforward. It iterates over all of the vertices on the graph and updates their distances.

When iterations are over, we get the shortest distances unless we have a negative weight cycle. Which would decrease the distance to negative infinity.

Time complexity: O(EV)

Here is the link of my C++ implementation of Bellman-Ford Algorithm: Bellman-Ford Algorithm

Author face

Abdurrezzak Efe

Bilkent University Bachelor's in CS 2018'

Recent post