Given a graph of v nodes (vertex) and a source vertex "src" in the graph, the task is to find the shortest paths from src to all vertices in the given graph.
The graph may contain negative weight edges.
Solutions
Method 1: Bellman-Ford Algorithm
Dijkstra doesn't work for graphs with negative weights; Bellman-Ford is used for such graphs.
Bellman-Ford is simpler than Dijkstra but the time complexity of Bellman-Ford, i.e., O(V * E) is more than Dijkstra's time complexity, i.e., O((V+E)LogV).
The Bellman-Ford algorithm includes the following steps:
Create an array shortestPaths[] and initializes distances from the source to all vertices as infinite and distance to the source itself as 0.
Repet the below steps v-1 times, where v is the number of vertices in the given graph.
If shortestPaths[j] + node.weight is less than shortestPaths[node.num], then update shortestPaths[node.num] to shortestPaths[j] + node.weight.
If we iterate through all the edges one more time and get a shorter path for any vertex, then there is a negative weight cycle.
Complexity
The time complexity of this solution is O(N*E) and space complexity is O(N).