#Algorithm Bellman Ford uses which algorithm design technique

Question

Is it Dynamic programming?

Answer 1

Bellman-Ford is also simpler than Dijkstra algorithm.

• Dijkstra doesn’t work for Graphs with negative weight edges.and it is greedy algo.

• Bellman ford work for negative edge weight. And it is a dynamic prog.

Comments

Small additional

Dijkstra's may/may not work for negative weight edge, it does not guarantee the correctness.

Answer 2

Yes. Bellman ford is an application of Dynamic Programming. 

https://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

Comments

@Deepakk

Can u plz tell me what dynammic programming actually mean?

I am very confused about which problem should be under dynamic programming and which one should not under dynamic programming

Plz tell me this point

---

what dynammic programming actually mean?

There is nothing in the name i.e. The Idea/Approach of Dynamic Programming(DP) can not be visualized from its name.  Dynamic Programming (DP) is an Idea/notion to solve (mostly) Optimization Problems. Just like other Paradigms/Notions like Divide and Conquer (Name itself reflects the Idea/approach of this Notion), Backtracking, randomization etc,  DP is also an approach to solve some Problems. There are so many problems in the world and we can not solve every problem with the same strategy/approach and that's why People come up with new ideas to solve a set of Problems. Each idea can only solve a small/big set of Problems. 

The informal idea of how DP solves problems is that it simplifies a complicated problem by breaking it down into simpler sub-problems in a recursive manner (So far sounds like Divide and Conquer only) But Dynamic programming applies when the subproblems overlap—that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

---

What's in the name??

From Quora https://www.quora.com/Why-is-dynamic-programming-called-dynamic-programming

---

which problem should be under dynamic programming and which one should not under dynamic programming
 

When the method applies? When should we look for a dynamic-programming solution to a problem? 

There are Two things that an Optimization problem must have in order for dynamic programming to apply: optimal substructure and overlapping subproblems.

Now this "Overlapping Subproblems" thing is easy to understand. Optimal Substructure is of more attention here. Both optimal substructure and overlapping subproblems are very well explained in  the Cormen After Matrix Chain Multiplication Problem under the Heading "Elements of dynamic programming".  

---

Dynamic Programming cannot solve all the Optimization Problems But it can solve (Polynomial time or Exponential time ) those Optimization Problems which possess the above Two properties i.e. optimal substructure and overlapping subproblems. 

For example, DP can not solve "Longest path Problem(LPP)" in the Graph because the Property "Optimal Substructure" doesn't hold good in this problem. It is (in very detailed manner) discussed in the Cormen why LPP violates Optimal Substructure Property and this very thing will give all the intuition needed to see When or When not DP can be applied.