Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Running Time Analysis

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 tex2html_wrap_inline70702 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 tex2html_wrap_inline71554 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 tex2html_wrap_inline70690. As a result, the worst-case time for each operation is tex2html_wrap_inline71558.

Thus, the worst-case running time for Dijkstra's algorithm is

displaymath71546

when adjacency lists are used, and

displaymath71547

when adjacency matrices are used to represent the input graph.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.