2 questions. first, why are you storing the direction? isn't that
implied in (V1,V2,dist)? (direction: V1>V2) unless you're storing each
edge twice for some caching purpose i'm not seeing?
second, by definition the longest path in a cyclic graph is infinitely
long. you need to convert it into a DAG.
once you've done that, the BellmanFord algorithm for shortest path will
work. just invert your distance values.
derek
Andrzej Bialecki wrote:
> Hi,
>
> I'm looking for an advice. I need to process a directed graph encoded as
> a list of <from, to> pairs. The goal is to compute a list of longest
> paths in the graph. There is no guarantee that the graph is acyclic, so
> there should be some mechanism to detect cycles.
>
> Currently I'm using a simple approach consisting of the following: I
> encode the graph as <vertex, <neighbor, direction, distance>>, and
> extending the paths by one degree at a time. This means that in order to
> find the longest path of degree N it takes N + 1 mapreduce jobs.
>
> Are you perhaps aware of a smarter way to do it? I would appreciate any
> pointers.
>
