分析

Floyd-Warshall算法的时间主要耗费在最小化函数上，时间为O(V3)，我们可以从这三层嵌套循环中看出来。例6-8中的constructShortestPath函数将会花费O(E)的时间，因为最短路径可能会经过图中的每一条边。