-----BEGIN PGP SIGNED MESSAGE----- Hash: RIPEMD160 On Sat, Dec 17, 2005 at 07:33:58PM +0100, Dmitry Bufistov wrote:
I have a non-directed, acyclical graph with a series of end points. I need to compute the longest path between any two end points. Right now I do this computing the longest dijkstra shortest path (using the boost graph library) from each end point and picking the longest of these, but this is quite heavy. Is there a faster way to do this ?
Hi, Unfortunately I didn't test, but I'm pretty sure, that for acyclic graphs Dijkstra's algorithm has linear complexity (you don't need color
If the graph is acyclic -> it is a tree -> there is 1 and only 1 path between any two vertices (consequently, it is both shortest and longest). So you might as well perform breadth-first search from a starting vertex to get all paths and distances to other vertices. BFS complexity is O(|A|) where |A| is the number of edges in the graph. If you need all-pairs paths, then you end up with O(|V|*|A|) with a naive algorithm (|V| time executing BFS from different end points), where |V| is the number of vertices. You can actually do better. You don't need to perform BFS for all vertices, but just for branching points (i.e. those whose degree is > 2). The rest of the vertices are just linear paths of constant length which can't affect path lengths between branch points (since you're dealing with a tree). Disclaimer: Its late at night and I haven't drawn any picture for myself. This is straight out of my head. Please double-check this. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFDpH7GFtofFpCIfhMRA0ofAJ98qRQcpBTphYRjgx0WDLfUCHP7fQCggTA4 hvASqnvtqUkOmKlu1mES59o= =UguX -----END PGP SIGNATURE-----