It is able to do this with Θ ( | V | 3 ) {\displaystyle \Theta (|V|^{3})} comparisons in a graph. This is remarkable considering that there may be up to Ω ( | V | 2 ) {\displaystyle \Omega (|V|^{2})} edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.