Re: [Boost-users] Graph problem -- solvable using the Boost graph library ?

From: zvrba_at_[hidden]
Date: 2005-12-17 16:10:30

-----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-----