Re: [Boost-users] Graph problem -- solvable using the Boost graph library ?
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 map at all), and you don't need to find all connected components, so your current approach is the best solution or very close to the best=) --dima
-----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-----
-----BEGIN PGP SIGNED MESSAGE----- Hash: RIPEMD160 On Sat, Dec 17, 2005 at 07:33:58PM +0100, Dmitry Bufistov wrote:
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
I would disagree. Dijkstra algorithm doesn't care about cycles. Its only prerequisite for correct operation is that all edge lengths are positive. Roughly, it does the following: 0. assign label 0 to start vertex, and infinity to all other vertices put U := V (V is the vertex set) 1. choose the vertex u from U such that u has minimum label and update weights of vertices reachable from u. the label is actually the distance to u from the starting vertex. 2. set U := U \ {u} and repeat until U is empty Step 1 is repeated |V| times. With primitive data structure for vertex labeling (such as array or linked list), the min operation takes O(|V|) so the total running time is O(|V|^2). If Fibonacci heap is used for computing the minimum, the running time can be reduced to O(|E|+|V|*log|V|). But in no case can the Dijkstra algorithm run in linear time. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFDpIH/FtofFpCIfhMRA2SiAJwOkGfD5VKc0LHRV6wdjsCW3GgOoQCeNLv7 UCPsS1gTgm13KMHHYa4R86s= =YlQc -----END PGP SIGNATURE-----
participants (1)
-
Dmitry Bufistov -
zvrba＠globalnet.hr