Geek asks and answers

The temporal complexity of the Floyd Warsall algorithm

The Skiena algorithm algorithm contains the following explanation of the Floyd Warsall 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 shortest path for all Floyd-Warshall pairs works in O (n 3 ) time, which is asymptotically no better than n Dijkstra's algorithm calls. However, the loops are such and the program is so short that in practice it works better. This is noteworthy as one of the rare graph algorithms that work better on adjacent matrices than adjacency lists.

Can someone explain why the bold part is true?

+5
source share
3 answers

, , .

, 2 . . n Djikstra's, , , . .

+2

- O (E log v), O (E + v log v), , factory , . .

, q-sort heap-sort

+2

, v - . ( ) e = O(v). ( ) e = O(v^2).

O(e + vlogv) . -, - . , node . , node . , .

, , e = O (v ^ 2), O(v^2 + vlogv)= O (v ^ 2). , ?

1:

Dijkstra .

? v * O (v ^ 2) = O (v ^ 3). , . ( ), , ( -) .

2:

- v * v. , , , . ( 2D-), v ^ 2 .

This needs to be done for each vertex. Therefore, the time complexity is O (v ^ 3) , but with a very small constant value, which makes it extremely viable during implementation.

So, all you need is a graph in the form of an adjacency matrix, another adjacency matrix for storing new values ​​and 3 nested loops that run throughout v * v * v times. I guess this is what is meant by stress and simple!

+1
source

More articles:


All Articles