•Re: Calculating Shortest Paths with Graph::Directed

in reply to Calculating Shortest Paths with Graph::Directed

One idea comes to mind... (but I'm not a math geek, so beware).

Duplicate the nodes that don't have a self-link, such as E1a and E1b. Add the same set of links to both E1a and E1b that you would have added to E1, but don't link E1a to E1b. Now look for a path from E1a to E1b, since it must go out and back first.

-- Randal L. Schwartz, Perl hacker

Comment on •Re: Calculating Shortest Paths with Graph::Directed

Replies are listed 'Best First'.
Re: •Re: Calculating Shortest Paths with Graph::Directed by arunhorne (Pilgrim) on Jul 19, 2002 at 16:09 UTC
Very lateral thinking! I've a feeling it would work, but unfortunately my real-life data set has 3097 vertextes and many more edges...!! I think my workstation is already going to have trouble without duplicating the work. Thanks though :) ____________ Arun	[reply]

In Section Seekers of Perl Wisdom