No. The normal Dijkstra's cannot be modified to work for longest path, as you can see the optimal subproblem problem is not satisfied. While the Dijkstra's shortest path can be computed in polynomial time, the longest path cannot be ( NP complete ). I'm sure there are lot of resources on net. May be you can start with wikipedia and the references given below ( http://en.wikipedia.org/wiki/Longest_path_problem ) :)
- AK On Mon, Jan 11, 2010 at 2:40 PM, Johan <djjord...@gmail.com> wrote: > Ok, so I know that Dijkstra can be used to solve the single-source > shortest path problem quite efficiently. I however need to find the > single source longest path through a graph. Can Dijkstra be used for > this if I transform the edge lengths so that the longest edge is now > the shortest etc etc. Does anybody have any references to work done > which is similar to the this longest path problem? > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > >--
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
