Thanks for all the feedback. My problem can be reduced to a directed acyclic graph (DAG) and as such the negation strategy should work to give me a longest path in polynomial time. I would like to if possible reduce the time taken to something less than polynomial time.
Thanks Anil for the reference to the Wikipedia page on the longest path problem, i did eventually find that myself. The biggest problem with the Wikipedia page is that it is sorely lacking in proper academic references. On Jan 15, 8:23 am, Miroslav Balaz <gpsla...@googlemail.com> wrote: > longest path can be solved in acyclic directed graphs. > so check your case if it is not that. > > 2010/1/15 Vivek S <s.vivek.ra...@gmail.com> > > > > > @chitta koushik > > No, That might lead to negative edge cycles! > > > 2010/1/15 chitta koushik <koushik.infin...@gmail.com> > > >> How abt negating values and using same single source shortest path algo ? > > >> 2010/1/15 saltycookie <saltycoo...@gmail.com> > > >>> longest path is NP-hard > > >>> 2010/1/11 Johan <djjord...@gmail.com> > > >>>> 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<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<algogeeks%2bunsubscr...@googlegroups > >> .com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > "Reduce, Reuse and Recycle" > > Regards, > > Vivek.S > > > -- > > 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.
