The Floyd-Warshall transitive closure algorithm is a dynamic programming algorithm: it makes use of many subproblem solutions to solve the whole problem. In particular, to know if there is a way to...

Extracted text: The Floyd-Warshall transitive closure algorithm is a dynamic programming algorithm: it makes use of many subproblem solutions to solve the whole problem. In particular, to know if there is a way to get from vertex A to B, what subproblem solutions does it use? OFor every other vertex X, see if there are paths from A to X and from X to B ODo a breadth first search to see if there is a path from A to B Do a depth first search to see if there is a path from A to B OCheck every path from A to B What's the runtime of the Floyd-Warshall transitive closure algorithm on a graph with N vertices, M edges O(N) Check O(N log N) O(M) O(N+M) O(N^2) O(N^3)