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. Andrzej Bialecki schrieb: > Hi, > > I'm looking for an advice. I need to process a directed graph encoded as > a list of <from, to> pairs. The goal is to compute a list of longest > paths in the graph. There is no guarantee that the graph is acyclic, so > there should be some mechanism to detect cycles. > > Currently I'm using a simple approach consisting of the following: I > encode the graph as <vertex, <neighbor, direction, distance>>, and > extending the paths by one degree at a time. This means that in order to > find the longest path of degree N it takes N + 1 map-reduce jobs. > > Are you perhaps aware of a smarter way to do it? I would appreciate any > pointers. >
