MADEEASY TEST SERIES

Question

Which of the following procedure is suitable to find the longest path from a given vertex  to any other given vertex in a directed acyclic graph (weighted) with few negative edge weights.

A Divide and conquer

B Greedy approach

C Dynamic programming.

D All of these

 ANSWER GIVEN IS C but why not gredy

Comments

Finding Longest Simple Path in a graph with non-negative edge weights is NP-Hard Problem.

Reason :- Since Finding the shortest simple path in a graph is NP-Hard. So, if we negate all the edges and apply bellman-ford , then there may be the case of negative weight cycle. So, Bellman-Ford may not compute the longest simple path in the graph. So Problem " Finding the shortest simple path in a graph" reduces to Problem "Finding Longest simple Path in a graph".Since 1st problem is NP-Hard . So, other problem will also be.

But if the graph is acyclic then  after negating the edges , we will not get any negative weight cycle. So, We can find the Longest Path in the acyclic graph easily using Bellman-Ford. 

Since , in the question , few edge weights are negative and few are non-negative . Since , graph is acyclic , so after negating the non-negative edge weights to negative edge weights , we will not get any negative weight cycle.  So, we we can apply Bellman-Ford algo easily and it follows Dynamic Programming paradigm . So, answer should be (C) 

---

Again a contradicting point coming here

bellman ford supports optimal substructure, but "Longest path Problem(LPP)" cannot support optimal substructure. Then how it solved by bellman ford?

---

ok mam, just forget that....

this problem can be solved bt multistage problem right ?

 

Multi stage problem is Dynamic Programming Concept.

Answer 1

This problem is for a single source longest path, with weighted negative edge, which can only be solved by bellman ford.

Bellman Ford works in greedy approach, not dynamic programming

Comments

From Where you read Bellman Ford is Greedy?

look at this https://gateoverflow.in/59487/is-bellman-ford-dynamic-programming-approach

---

@Shaik

yes , many links it is told as dynamic programming

but See this https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/readings/

here it is told minimum spanning tree finding is a greedy approach

right?

that is why , i thought it could be both dynamic as well as greedy

---

mam, minimum spanning tree finding is a greedy approach, it's ok,

but how you conclude bellman ford is greedy from above statement.