Derek Anderson wrote:
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?
That's a side effect of my primitive implementation. I store the same pair twice, once as a forward and once as a reversed edge, so that I can do joins in reduce(), to tack on the next segment of the path.
second, by definition the longest path in a cyclic graph is infinitely long. you need to convert it into a DAG.
I understand that I need to break cycles. But first I need to identify them, and it's not obvious (yet) to me how to do it.
once you've done that, the Bellman-Ford algorithm for shortest path will work. just invert your distance values.
Thanks, I'll look it up. -- Best regards, Andrzej Bialecki <>< ___. ___ ___ ___ _ _ __________________________________ [__ || __|__/|__||\/| Information Retrieval, Semantic Web ___|||__|| \| || | Embedded Unix, System Integration http://www.sigram.com Contact: info at sigram dot com
