Time complexity of Floyd Warshall algorithm

Question

The Skiena's book of algorithm contains the following explaination of Floyd Warshall algorithm:

 floyd(adjacency_matrix *g)
 {
   int i,j; /* dimension counters */
   int k; /* intermediate vertex counter */
   int through_k; /* distance through vertex k */
   for (k=1; k<=g->nvertices; k++)
       for (i=1; i<=g->nvertices; i++)
           for (j=1; j<=g->nvertices; j++) {
                through_k = g->weight[i][k]+g->weight[k][j];
                if (through_k < g->weight[i][j])
                      g->weight[i][j] = through_k;
           }
  }

The Floyd-Warshall all-pairs shortest path runs in O(n³) time, which is asymptotically no better than n calls to Dijkstra’s algorithm. However, the loops are so tight and the program so short that it runs better in practice. It is notable as one of the rare graph algorithms that work better on adjacency matrices than adjacency lists.

Can someone please elaborate why the bold part is true?

Solution 1

Let's break it down:

The Floyd-Warshall all-pairs shortest path runs in O(n³) time ...

This is because we have a triple for loop, each with n iterations to make

... which is asymptotically no better than n calls to Dijkstra’s algorithm. ...

Recall that a single call to Dijkstra's algorithm will tell us all the shortest paths from one particular node, x1, to all nodes in the graph. We can therefore make n calls to Dijkstra's algorithm for all nodes in the graph: x1, x2, ... xn to find the shortest paths from x1 to all nodes, x2 to all nodes, ... xn to all nodes. In other words, this gives us all pairs shortest paths – just like Floyd Warshall does!

Running Dijkstra n times:
time = number of nodes × O((n + e)lgn)      [assuming binary heap used for Dijkstra]
     = n × O((n + e)lgn)                
     = O(n(n + e)lgn)

And so it is indeed the case that the O(n^3) time of Floyd-Warshall is not better than the O(n(n + e)lgn) time of making n calls to Dijkstra.

... However, the loops are so tight and the program so short that it runs better in practice.

The key words here are "in practice". Remember, asymptotic analysis isn't perfect. It's a mathematical abstraction / approximation for performance. When we actually come to run the code, there are many practical factors that it did not take in account. The processor has a complex low-level architecture for fetching and running instructions. It pipelines instructions, pre-fetches instructions, attempts to predict instructions, caches instructions and data, ... it's quite unpredictable! And yet, all of these low-level optimisations can have a massive impact on the overall performance of an algorithm. Algorithms that are theoretically slow can receive a boost, and algorithms that are theoretically quick might not receive the same boost. This is sometimes called the hidden constant factor of the big-oh notation.

It turns out that processors love optimizing nested for loops and multi-dimentional arrays! This is what Skiena is alluding to here. The for loops the array makes the best use of temporal and spacial locality and work well with low-level processor optimizations. Dijkstra's algorithm on the other hand doesn't do this as well and so the processor optimisations don't work as well. As a result Dijkstra could indeed be slower in practice.
Floyd-Warshall is a "short program" in the sense that is isn't using any sophisticated data structures and the number of instructions to repeat is small. These things, along with the processor optimizations contribute to Floyd-Warshall having a small hidden constant factor. That is to say, the k in O(k · n³) is small.

Solution 2

Assume v to be the number of vertices. For a sparse graph (few edges) the number of edges e = O(v). For a dense graph (many edges) e = O(v^2).

Now the best asymptotic implementation of the shortest path problem from a single source takes O(e + vlogv) amortized time. This implementation of the Dijkstra's algorithm uses Fibonacci Heaps, which are not very practical because of the high constant values involved. For instance, apart from the parent and children, every vertex in the heap is also connected to its sibling node using a double linked list. This leads to each node storing a lot of pointers. Apart from the heap, even the adjacency list needs to be accessed for every vertex.

If we assume the worst case scenario where our graph turns out to be a dense graph, e = O(v^2), Dijkstra's algorithm will take O(v^2 + vlogv) = O(v^2). Now how would you find the shortest path between all pairs of vertices?

Option 1:

You could go with Dijkstra's algorithm and apply it for every single vertex.

How much would that cost? v * O(v^2) = O(v^3). However, the constants involved would make the practical cost higher. You'll have to build the heap (once), check the adjacency list, decrease-key and extract the minimum(while maintaining the min-heap) for every vertex.

Option 2:

The Floyd-Warshall algorithm basically works on a v * v adjacency matrix. It considers every vertex and decides what would be the shorter route if could you go via that vertex. This is a constant time comparison and an insert-operation (into a 2D array) carried out for all v^2 elements of the matrix.

This needs to be performed for every vertex. Therefore the time complexity comes out to be O(v^3) but with a very small constant value, making it extremely viable during implementation.

So all you need is the graph in the format of an adjacency matrix, one more adjacency matrix to store the new values and 3 nested for loops that run for a total of v * v * v times. I'm guessing this is what is meant by tight and simple!

Solution 3

However, the loops are so tight and the program so short that it runs better in practice.

If you look at that algorithm, there are three loops and only 2 statements nested inside of those. The only logic is done within the third nested loop. If you ran n Djikstra's, the logic would be done inside the first loop as well as the lasted nested, which is easily debatably not cleaner. With the clean three loops the computer should have an easier time managing the memory as well.

Solution 4

Dijkstra's algorithm with common data structure is O(E log v) but Fibonacci heap improves this to O(E+v log v) which is more complicated data structure and constant factory of algorithm is bigger than floyed. look at Running time in this link.

the difference in this question is as same as diffrence between q-sort and heap-sort

View more solutions