|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The running time of the DijkstrasAlgorithm method
is dominated by the running time of the main loop (lines 13-33).
(It is easy to see that lines 5-9 and 34-39 run in 
time).
To determine the running time of the main loop,
we proceed as follows:
First, we ignore temporarily the time required for the Enqueue
and Dequeue operations in the priority queue.
Clearly, each vertex in the graph is processed exactly once.
When a vertex is processed all the edges emanating from it are considered.
Therefore, the time (ignoring the priority queue operations) taken
is O(|V|+|E|) when adjacency lists are used and
when adjacency matrices are used.
Now, we add back the worst-case time required
for the priority queue operations.
In the worst case, a vertex is enqueued and subsequently dequeued
once for every edge in the graph.
Therefore, the length of the priority queue is at most 
.
As a result, the worst-case time for each operation is 
.
Thus, the worst-case running time for Dijkstra's algorithm is
when adjacency lists are used, and
when adjacency matrices are used to represent the input graph.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.