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 Bellman-Ford 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 map-reduce jobs.
Are you perhaps aware of a smarter way to do it? I would appreciate any
pointers.
