Problem
The Floyd-Warshall algorithm for the All-Pairs Shortest Path problem.
1. What problem is the algorithm is trying to solve? What does it mean to solve the problem/What is the output of the algorithm? Is this output the best solution, or an approximation?
2. Why does the algorithm work? How? Be specific; you shouldn't give pseudocode, but you might write (for example) "loop through each node and add up the weights of all incoming and outgoing edges".
3. What is the run time complexity of this algorithm? Justify your answer using the algorithm description you gave above.