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