The implementation for Floyd's algorithm is inefficient for adjacency lists because the edges are visited in a bad order when initializing array \(\mathrm{D}\). What is the cost of of this initialization step for the adjacency list? How can this initialization step be revised so that it costs \(\Theta\left(|\mathbf{V}|^{2}ight)\) in the worst case?

Floyd's Algorithm:

Transcribed Image Text:

// Compute all-pairs shortest paths static void Floyd (Graph G, int [] [] D) { for (int i=0; i