sir how dp is used ye samjh nhi aa rha h i also read article on sanfoundary but nhi ho aa rh h pliz help
Bellman Ford Algo qns
@sgdon142 hey,I will explain you basically belmen ford is use to find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.
Here are the steps:
1 Initializes distances from source to all vertices as infinite and distance to source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src is source vertex.
2 Now calculate shortest distances .now for every edge u-v do this v-1 times where v are vertices number:
If dist[v] > dist[u] + weight of edge uv, then update dist[v]
dist[v] = dist[u] + weight of edge uv
This is updation of dp array to update minimum weight
3 Graph should not contain negative weight cycle such that its weight should not be negative so check this:
Do following for each edge u-v
If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”
This algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-most 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle.
Hope you get it ,if you have more doubt than call me on 7015208814 ,I will explain thoroughly to explain you concept.
Happy coding 