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.


Reply via email to