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
