Bellman Ford Algorithm For Negative Edge Weights And Cycles Detection
Bellman-ford algorithm finds single source shortest path in directed graphs with negative edge weights. It also detects negative cycles. Time complexity: O(n*m).
Bellman-ford algorithm
Bellman ford algorithm works on directed graph only ( if you want to use it on undirected graph then you will have
to convert the undirected graph into directed graph first)
Bellman ford algorithm is used to find the single source shortest path even when the graph has negative edge weight(in
which case Dijkstra's fails)
Bellman ford also helps us check if the graph(DAG) has negative edge cycle
What needs to be done:
Relaxation of edges:
if(distance[u] + weight < distance[v]){
distance[v] = distance[u] + weight;
}
This above check needs to...