Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email email@example.com
From: Dmitri Krioukov (dimaKRIOUKOV.NET)
Date: Mon Aug 06 2001 - 17:00:18 CDT
This is actually very simple and can be found elsewhere.
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|)),
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
> -----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