Can we modify Dijkstra algorithm for computing maximum distance problem

Question

Following statement is true or false?
If we make following changes to Dijkstra, then it can be used to find 
the longest simple path, assume that the graph is acyclic.

1) Initialize all distances as minus infinite instead of plus infinite.

2) Modify the relax condition in Dijkstra's algorithm to update distance
of an adjacent v of the currently considered vertex u only
if "dist[u]+graph[u][v] > dist[v]". In shortest path algo, 
the sign is opposite. 
(A) True
(B) False

I think it must be true but answ given is false , its says that In shortest path algo, we pick the minimum distance vertex from the set of vertices for which distance is not finalized yet. And we finalize the distance of the minimum distance vertex.
For maximum distance problem, we cannot finalize the distance because there can be a longer path through not yet finalized vertices.

Now I am nt getting that when all are initialized with minus infinty so then maximum can be found , so then whats the issue why cant we finalize it ?

Answer 1

Longest simple path cannot be computed like this. To understand why you need to know that Dijikstra's algorithm works using Greedy principle. That is, at each vertex we choose the best neighbour and include that in the shortest path. Doing like this in end, we get the best path- greedy approach works. But this approach need not work in many cases and longest path one is just an example. A simple example can be shown as follows. 

Consider shortest path from a-c

Comments

finding the longest path is similiar to finding the hamillton ckt in the graph or travelling salesman  problem which is np hard.no algo possible right??

---

NP-hard doesn't mean no algorithm possible. All NPC problems are NP-hard also and all of them have algorithms that take polynomial time with a non-deterministic TM. Also, there are problems outside NPC that have algorithm that takes super polynomial time even with a non-deterministic TM. NPH is not same as undecidable.

---

@ Arjun sir ...i wanted to say that by just doing little modification we can not change the complexity of an algo entirely.So ,if we are finding the soln  of a problem which is np hard (longest path in a graph) then we can do it by an algo having extreamly large rising time complexity fun but cant solve it by modifying an algo with time complexity like 0(n^2) or some other slowly growing fun.because the resultant algo will be 0(n^2)

sir,plz notify me if my statement is still wrong..

Answer 2

finding shortest path is polynomial time while longest path is a NPC . which are the hardest problem. no polynomial time solution exists till now for it. because longest path will contain the path which will cover as much distance as possible .and it algo will take n^n time . while if u us the dijisktra . it will just end up with a wrong answer. yd rakhne ka best way . am ne kaha jaldi ghar a jao u will say 5 min me a jayunga . limit on time algo is there but agar ma ne kaha kabhi bhi ana . then i may come in 1 hour , 1year , 100 year or never come . no time bound procedure exist .