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 (URLs) 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
