Question:
Floyd-Warshall all pairs shortest paths algorithm
This problem is about the Floyd-Warshall all pairs shortest paths algorithm.
A. What is the running time of the algorithm?
B. The algorithm computes values dk(i,j). Explain in words what dk(i,j) means - explain what each of the variables i, j, k and dk(i,j) represents.
C. For the graph sketched below, compute the values of d0(3,2), d1(3,2), d2(3,2), d3(3,2), d4(3,2).