Logo 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_inline71729 (lines 6-9). Transferring the weights from the input graph to the distance matrix requires tex2html_wrap_inline71915 time if adjacency lists are used, and tex2html_wrap_inline71729 time when an adjacency matrix is used to represent the input graph (lines 10-19).

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


next up previous contents index

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