##### Site index · List index
Message view
Top
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

Mime
View raw message