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

From: zvrba_at_[hidden]
Date: 2005-12-17 16:24:15

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