hadoop-common-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Andrzej Bialecki ...@getopt.org>
Subject Re: Finding longest path in a graph
Date Sat, 31 Jan 2009 20:42:16 GMT
Mork0075 wrote:
> In general you can find shotest paths with the algorithm of Diskstra in
> O(m + n log n) where m is the number of edges and n the number of nodes.
> If you modify the Diskstra you should also be able to calculate longest
> paths (instead of cheacking if the new path is smaller then the old one,
> you can check if its longer). As datastructure you need a priority
> queue, which returns the "current longest node" instead of shortest.
> For azyklic graphs there is some other algorithm, which first calculates
> a topological sorting for all nodes. With the topo sort you can also
> check if there are cycles. Check for cylce detection and DFS (depth
> first search). After this you process the nodes in topo sort order. Then
> you will check for each child node their distance and chose the
> maximum(allChildren). This can be done in O(m+n)
> Perhaps this helps.

Thank you, I think this confirms my understanding of the problem.

Currently the implementation I have executes in N + 2 steps, and if 
there are cycles with diameter less than N, the vertices that are part 
of the cycle get m*N distance metric, which helps to detect cycles 
(because all valid paths have the metric at most N). Based on the 
specific nature of the graph (URL-s) I break the cycles by selecting the 
shortest URL as the start, and removing the edge from the last 
predecessor, which then becomes the end.

Best regards,
Andrzej Bialecki     <><
  ___. ___ ___ ___ _ _   __________________________________
[__ || __|__/|__||\/|  Information Retrieval, Semantic Web
___|||__||  \|  ||  |  Embedded Unix, System Integration
http://www.sigram.com  Contact: info at sigram dot com

View raw message