Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline70371 (lines 6-9). Transferring the weights from the input graph to the distance matrix requires tex2html_wrap_inline70567 time if adjacency lists are used, and tex2html_wrap_inline70371 time when an adjacency matrix is used to represent the input graph (lines 11-18).

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


next up previous contents index

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