Bin,

This is actually very simple and can be found elsewhere.
Briefly:
1) If you use a list representation then to find
the minimum takes O(|V|). Thus, it takes O(|V|^2) total
over the run. Plus you need O(|E|) decreases. Altogether
O(|E|+|V|^2). If the graph is dense (|E|=O(|V|^2)), this
implementation is optimal. If the graph is sparse (|E|=O(|V|)),
it's not.
2) If you use a priority queue representation (heaps of
any kind except Fibonacci), then every find minimum and
every decrease takes O(log|V|), or O((|E|+|V|)log|V|)
over the run. For sparse graphs, it's more optimal
(O(|E|log|V|) vs. O(|V|^2)).
3) It can be shown (which is a little bit more complicated)
that amortized running time of static Dijkstra with Fibonacci
heap representation of sparse graphs is O(|E|+|V|log|V|),
which is yet a little bit better but requires significant
constant memory overhead.

I'd further refer you to the Dijkstra improvements
(known as dynamic or incremental SPF algorithms). See
http://citeseer.nj.nec.com/330582.html and references
therein.

--
dima.
> -----Original Message-----
> From: Mailing List [mailto:OSPFDISCUSS.MICROSOFT.COM]On Behalf Of Bin
> Liu
> Sent: Friday, August 03, 2001 10:56 AM
> To: OSPFDISCUSS.MICROSOFT.COM
> Subject: a student's question 3 (Dijkstra's)
>
>
> Hi,
>
> Would you please tell me where I can find more details about the
> processing
> time for a n-node Dijkstra's computation . So far, I only know that
> (1) the complexity of the n-node Dijkstra's computation is  n*log (n)
> (2) Steve Deering, in his ¡°MOSPF meeting report¡±, presented the
> following
> statistics: for a 200 routers network, the time to run Dijkstra in a DEC
> 5000 (10 MIPS processor) was around 15 milliseconds.
>
> Similarly, could you tell me how to trace the number of instructions a n-
> node Dijkstra's computation may need.
>
> Best wishes
>
> yours
> Ben

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]