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

Running Time Analysis

The worst-case running time for Floyd's algorithm is easily determined. Creating and initializing the distance matrix is tex2html_wrap_inline70626 (lines 6-9). Transferring the weights from the input graph to the distance matrix requires tex2html_wrap_inline70822 time if adjacency lists are used, and tex2html_wrap_inline70626 time when an adjacency matrix is used to represent the input graph (lines 11-14).

The running time for the three nested loops is tex2html_wrap_inline71074 in the worst case. Finally, constructing the result graph and transferring the entries from the distance matrix to the result requires tex2html_wrap_inline70626 time. As a result, the worst-case running time of Floyd's algorithm is tex2html_wrap_inline71074.


next up previous contents index

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